14

私は現在、Just In Time（JIT）コンパイラでさまざまなアルゴリズムを実装しようとしています。アルゴリズムの多くは、ビットセット（より一般的にはビットセットとして知られています）で動作します。

C ++では、ビットセットを実装するさまざまな方法があります。真のC++開発者として、私はSTLの何かを使用したいと思います。最も重要な側面はパフォーマンスです。動的にサイズ変更可能なビットセットは必ずしも必要ではありません。

私が見ているように、3つの可能なオプションがあります。

I. 1つのオプションはstd::vector<bool>、スペース用に最適化されたを使用することです。これは、データがメモリ内で連続している必要がないことも示します。これによりパフォーマンスが低下する可能性があると思います。一方、ブール値ごとに1ビットを使用すると、キャッシュに非常に適しているため、速度が向上する可能性があります。

II。別のオプションは、代わりにを使用することstd::vector<char>です。データがメモリ内で連続していることを保証し、個々の要素へのアクセスが容易になります。ただし、このオプションはビットセットを意図したものではないため、このオプションを使用するのは奇妙に感じます。

III。3番目のオプションは、実際のを使用することstd::bitsetです。動的にサイズ変更できないという事実は問題ではありません。

最大のパフォーマンスを得るにはどちらを選択すればよいですか？

4

3 に答える 3

8

すべての状況が異なるため、最良の方法はそれをベンチマークすることです。

私は使用しませんstd::vector<bool>。一度試してみましたが、パフォーマンスはひどいものでした。std::vector<char>代わりに使用するだけで、アプリケーションのパフォーマンスを向上させることができます。

とはあまり比較std::bitsetしませんでしstd::vector<char>たが、スペースに問題がなければ、に行きstd::vector<char>ます。ビットセットの8倍のスペースを使用しますが、データを取得または設定するためにビット演算を実行する必要がないため、より高速になるはずです。

もちろん、ビットセット/ベクトルに大量のデータを格納する必要がある場合は、プロセッサのキャッシュに収まるため、ビットセットを使用すると便利な場合があります。

最も簡単な方法は、typedefを使用し、実装を非表示にすることです。ビットセットとベクトルの両方が[]演算子をサポートしているため、一方の実装をもう一方の実装に簡単に切り替えることができます。

于 2012-07-29T20:21:02.283 に答える
5

私は最近このフォーラムで同様の質問に答えました。私のBITSCANライブラリをお勧めします。バージョン1.0をリリースしました。BITSCANは、高速ビットスキャン操作用に特別に設計されています。

BitBoardクラスは、64ビットワード（別名ビットボード）のbsf、bsr、popcountなど、一般的な操作のさまざまな実装をラップします。クラスBitBoardN、BBIntrin、およびBBSentinelは、ビットスキャンをビット文字列に拡張します。BITSCANのビット文字列は、ビットボードの配列です。ビット文字列の基本ラッパークラスはBitBoardNです。BBIntrinは、64ビットボードを超えるWindowsコンパイラ組み込み関数を使用してBitBoardNを拡張します。BBIntrinは、適切なasmと同等の関数を使用することにより、POSIXに移植可能になります。

私はBITSCANを使用して、グラフ領域のNP組み合わせ問題に対して多数の効率的なソルバーを実装しました。通常、グラフの隣接行列と頂点セットはビット文字列としてエンコードされ、通常の計算はビットマスクを使用して実行されます。単純なビットコード化されたグラフオブジェクトのコードは、GRAPHで利用できます。BITSCANとGRAPHの使用例もあります。

BITSCANと、STL（ビットセット）およびBOOST（dynamic_bitset ）の一般的な実装との比較は、 http ： //blog.biicode.com/bitscan-efficiency-at-glance/にあります。

于 2014-07-22T18:39:28.273 に答える
1

この（やや古い）論文にも興味があるかもしれません： http ：//www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

[更新]前のリンクは壊れているようですが、この記事を指していると思います： https ://www.researchgate.net/publication/220803585_Performance_of_C_bit-vector_implementations

于 2014-01-03T19:58:47.553 に答える