我四处搜索,找不到 bitset::count() 的性能时间规范。有谁知道它是什么(O(n)或更好)以及在哪里可以找到它?
由 STL编辑我只指标准模板库。
我四处搜索,找不到 bitset::count() 的性能时间规范。有谁知道它是什么(O(n)或更好)以及在哪里可以找到它?
由 STL编辑我只指标准模板库。
我在我的电脑上阅读了这个文件(C:\cygwin\lib\gcc\i686-pc-cygwin\3.4.4\include\c++\bitset)。
看到这些
/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }
size_t
_M_do_count() const
{
size_t __result = 0;
for (size_t __i = 0; __i < _Nw; __i++)
__result += __builtin_popcountl(_M_w[__i]);
return __result;
}
顺便说一句,这是指定 _Nw 的地方:
template<size_t _Nw>
struct _Base_bitset
因此在 gcc 实现中它是 O(n) 。我们得出结论,规范并不比 O(n) 更好。没有人会以比这更糟糕的方式实施它。然后我们可以安全地假设它最坏的情况是 O(n)。可能更好,但你永远不能指望它。
由于 C++ 社区中普遍滥用该术语,我无法确定您在这里所说的“STL”的真正含义。
C++ 标准(2003 年)没有要求(或者,事实上,据我所知std::bitset::count()
,任何成员)的性能。std::bitset
我也找不到任何建议对 STL 的性能进行授权的参考资料bitset::count()
。
不过,我认为任何理智的实现都会在恒定(或最坏的线性)时间内提供这一点。然而,这只是一种感觉。检查你的,看看你会得到什么。
“SGI 的参考实现相对于存储位所需的字节数以线性时间运行。它通过创建一个由 256 个整数组成的静态数组来实现这一点。存储在数组中第 i 个索引处的值是在值 i。”
我不确定您是否会为此找到规范,因为 STL 通常不需要一定的性能水平。我已经看到它“快速”的提示,在集合的大小中每比特大约 1 个周期。您当然可以阅读您的特定实现的代码以了解预期结果。
我们遵循的算法是计算所有设置为 1 的位。现在,如果我们想通过该位集来计算数字 n,我们将通过 log(n)+1 位。
例如:对于数字 13,我们得到 1101 作为 bitset。
13 的自然对数 = 2.564(大约)3
位数 = 3+1 = 4
对于任何数字 n(十进制),我们循环 log(n)+1 次。
另一种方法如下:
int count_set_bits_fast(int n) {
int count = 0;
while (n > 0) {
n=(n&(n-1));
count++
}
return count;
}
如果分析功能线n=(n&(n-1)); 你会发现它基本上从右到左减少了位数。
因此,顺序将是总设置位的数量。
例如:13 = 1101
1101&1100 = 1100
1100&1011 = 1000
1000&0111 = 0
O(设置位数),O(Log(n)+1)最坏情况