13

我四处搜索,找不到 bitset::count() 的性能时间规范。有谁知道它是什么(O(n)或更好)以及在哪里可以找到它?

由 STL编辑我只指标准模板库。

4

5 回答 5

11

我在我的电脑上阅读了这个文件(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)。可能更好,但你永远不能指望它。

于 2011-01-14T17:14:13.303 回答
1

由于 C++ 社区中普遍滥用该术语,我无法确定您在这里所说的“STL”的真正含义。

  • C++ 标准(2003 年)没有要求(或者,事实上,据我所知std::bitset::count(),任何成员)的性能。std::bitset

  • 我也找不到任何建议对 STL 的性能进行授权的参考资料bitset::count()

不过,我认为任何理智的实现都会在恒定(或最坏的线性)时间内提供这一点。然而,这只是一种感觉。检查你的,看看你会得到什么。

于 2011-01-14T17:16:40.273 回答
0

“SGI 的参考实现相对于存储位所需的字节数以线性时间运行。它通过创建一个由 256 个整数组成的静态数组来实现这一点。存储在数组中第 i 个索引处的值是在值 i。”

http://www.cplusplus.com/forum/general/12486/

于 2011-01-14T17:08:20.473 回答
0

我不确定您是否会为此找到规范,因为 STL 通常不需要一定的性能水平。我已经看到它“快速”的提示,在集合的大小中每比特大约 1 个周期。您当然可以阅读您的特定实现的代码以了解预期结果。

于 2011-01-14T17:09:43.227 回答
0

我们遵循的算法是计算所有设置为 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)最坏情况

于 2021-08-06T03:02:41.733 回答