13

あちこち検索しましたが、bitset::count() のパフォーマンス時間の仕様が見つかりませんでした。それが何であるか(O(n)以上)、どこで見つけられるか知っている人はいますか?

EDIT By 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

STL は通常、特定のレベルのパフォーマンスを必要としないため、その仕様が見つかるかどうかはわかりません。セットのサイズでビットあたり約 1 サイクルの「高速」であるというヒントを見てきました。もちろん、特定の実装のコードを読んで、何が期待できるかを知ることができます。

于 2011-01-14T17:09:43.227 に答える
0

「SGI の参照実装は、ビットを格納するために必要なバイト数に関して線形時間で実行されます。これは、256 の整数の静的配列を作成することによって行われます。配列の i 番目のインデックスに格納される値は、値 i."

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

于 2011-01-14T17:08:20.473 に答える