假设我有一个问题，我想计算大量的双精度数，每次我计算一个新的双精度数时，我想检查一下我以前是否见过这个双精度数。做这件事最好(最快)的方法是什么?
如果双精度是精确的，我将创建一个set并检查成员是O(log n)，或者是一个O(1)的哈希集。但是它们不是精确的，因此我需要遍历所有之前看到的double，并检查它们是否在新计算的double的容差范围内，这是缓慢的:O(n)。我的想法是只保留双精度数的前30位，在集合中给出2^-30的精度，并检查它们是否相等。这是个好主意还是有更好的办法?那么如何只保留双精度数的最高30位呢?
无论采用哪种四舍五入模式，您都将始终绘制一条线，并且落在线的一侧或落在另一侧的数字可以任意接近(Float的情况下为1 up)。
因此，您需要使用至少两个具有不同舍入模式的集合，并检查具有一种舍入模式或另一种模式的浮点数是否在集合中。
例如，对于容差t，它将是这样的:
is_close = ( round(x,t) is in set1) or ( round(x+t/2,t) is in set2 )
set1 add round(x,t)
set2 add round(x+t/2,t)
我建议使用地板或天花板作为截断模式的规则。
注1:对于整型n和小型0 < eps < t/100,n*t+t-eps和n*t-t+eps均认为接近，距离接近2 t，故上式中应选用t作为半公差。
注2:这是一个绝对的公差。如果目的是相对容差(截断有效位-即降低精度)，那么处理二进制边界的公式可能会涉及更多，但应该应用相同的算法(只是t将是浮动的…)
如果您需要确定您以前是否在某个范围(a到b)内看到过给定的值，那么您可以使用所有以前看到的值的std::set来做到这一点。我们可以使用upper_bound()找到第一个大于a的元素，然后测试它是否小于b:
// untested
bool have_seen(const std::set<double>& past, double a, double b)
{
auto it = past.upper_bound(a);
return it != past.end() && *it < b;
}
(如果要测试包含范围，请使用lower_bound和<=)
速度当然是0 (logn)
您可以选择std::nextafter的几个迭代来获得适合您的值的a和b。
如果您确实需要降低双精度数的精度(并且不清楚这是否是针对您的特定问题的解决方案)，那么如果您的系统使用通用的标准二进制格式，则不会太困难。
我们可以利用最低有效数字包含尾数的事实，并将这些数字的正确数量设置为0:
#include <cstdint>
#include <limits>
double trunc(double d, int precision) noexcept
{
// This function requires IEEE-754 binary representations
static_assert(std::numeric_limits<double>::is_iec559);
static_assert(std::numeric_limits<double>::radix == 2);
using Integer = std::uint_fast32_t;
static const auto max_precision = std::numeric_limits<double>::digits;
if (precision < 1) {
// invalid
return 0;
}
if (precision >= max_precision) {
// no-op
return d;
}
auto& i = reinterpret_cast<Integer&>(d);
static_assert(sizeof i >= sizeof d);
auto mask = ~Integer{} << (max_precision - precision);
i &= mask;
return d;
}
示范:
#include <iostream>
int main()
{
for (double d: {100, 101, 102, 103, 104, 105, 106,
200, 202, 206, 207, 208, 209, 210}) {
std::cout << d << " -> " << trunc(d, 5) << 'n';
}
}
100 -> 100
101 -> 100
102 -> 100
103 -> 100
104 -> 104
105 -> 104
106 -> 104
200 -> 200
202 -> 200
206 -> 200
207 -> 200
208 -> 208
209 -> 208
210 -> 208
这是否真的是你需要的很难说。如果您想将结果收集到直方图桶中，它可能很有用:
#include <iostream>
#include <iomanip>
#include <map>
#include <random>
#include <string>
int main()
{
std::mt19937 gen(std::random_device{}());
std::normal_distribution<double> dist(0.5,0.1);
std::map<double,std::size_t> histogram;
for (int i = 0; i < 10000; ++i) {
auto d = trunc(dist(gen), 5);
++histogram[d];
}
for (auto const& [value, freq]: histogram) {
std::cout << std::fixed << std::setprecision(3) << std::setw(5)
<< value << ": " << std::string(freq/50, '*') << 'n';
}
}
0.203:
0.211:
0.219:
0.227:
0.234:
0.242:
0.250:
0.266:
0.281: *
0.297: *
0.312: **
0.328: ***
0.344: ***
0.359: *****
0.375: ******
0.391: *******
0.406: ********
0.422: *********
0.438: **********
0.453: ***********
0.469: ************
0.484: ************
0.500: *************************
0.531: **********************
0.562: ******************
0.594: **************
0.625: *********
0.656: *****
0.688: **
0.719: *
0.750:
0.781:
0.812:
0.844:
虽然这个正态分布看起来偏斜，但这只是因为当指数增加时，桶大小在0.5处发生变化。
这里有一个方法，即使你不能在RAM中保存所有的双精度浮点数，也可以工作。
- 收集double列表。O (N)
- 排序。O (N * logN)
- 扫描列表。对于每个项目，输出或丢弃它，取决于它与最后一个输出值的接近程度。O (n)
如果test for 'close'"是昂贵的，注意这个算法只执行N次测试。一些提出的算法是O(N*M)，其中N是输入计数，M是输出计数。
进一步注意，输出是不确定的。我的意思是，重新排列输入列表可能会改变，哪些双精度值被保留，哪些被丢弃。此警告可能适用于任何和所有算法。