STL Bitset :: Count（）メソッドのパフォーマンスは何ですか？

StackOverflow https://stackoverflow.com/questions/4693747

  •  11-10-2019
  •  | 
  •  

質問

私は周りを検索しましたが、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」とはどういう意味かはわかりません。

  • std::bitset::count() （または、実際、のメンバー std::bitset 私が見る限り）。

  • STLのパフォーマンスの委任状を示唆する参照が見つかりません bitset::count() また。

「SGIの参照実装は、ビットの保存に必要なバイト数に関して線形時間で実行されます。これは、256整数の静的配列を作成することでこれを行います。アレイにITHインデックスに保存されている値は、セットされたビット数です。価値i。」

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top