1

現在、大量のビットマップ情報を格納するために、1 つの大きなビットセットを使用するか、64 ビットの符号なし long (uint_64) を多数使用するかを検討しています。この場合、ビットマップは数 GB のメモリ ページの現在のステータス (ダーティ/ダーティではない) を表し、何千ものエントリがあります。

私が実行している作業では、2 つのダーティ ページ ビットマップ間で OR 操作を実行するなど、ダーティ ページをクエリおよび更新できる必要があります。

明確にするために、次のことを実行します。

  • ファイルからビットマップをインポートし、既存のビットマップでビット単位の OR 演算を実行する
  • ハミング重みの計算 (ダーティ ページの数を表す 1 に設定されたビットの数をカウント)
  • 少しリセット/クリアして、更新済み/クリーンとしてマークします
  • ビットの現在のステータスをチェックして、クリーンかどうかを判断する

C++ ビットセットでビット単位の操作を実行し、ハミングの重みを簡単に計算するのは簡単なようです。ただし、ここには魔法はないと思います-CPUは、レジスタに格納できるバイト数に対してのみビット単位の操作を実行できます-したがって、ビットセットで使用されるルーチンは、私が実装するのと同じです。これはおそらくハミング重みにも当てはまります。

さらに、ビットマップ データをファイルからビットセットにインポートするのは見た目が悪いです。ここに示すように、ビットシフトを複数回実行する必要があります。使用するビットセットのサイズを考えると、これはパフォーマンスに悪影響を与えると思います。もちろん、代わりに多くの小さなビットセットを使用することもできると思いますが、これには利点がないかもしれません (おそらく実装の容易さ以外)。

いつものように、どんなアドバイスも歓迎します。ありがとう！

4

3 に答える 3

1

非常に特殊な使い捨てアプリケーションがあるようです。個人的にはビットセットを使用したことはありませんが、その利点は、まるでブールの配列であるかのようにアクセスできることと、ベクトルのように動的に成長できることです。

私が収集できることから、あなたはそれらのどちらも実際には必要ありません。それが事実であり、ビットセットの入力がドラマである場合、整数の束全体を割り当ててそれらに対してビット演算を実行するのは非常に簡単であるため、私は自分でそれを行う傾向があります。

非常に具体的な要件があることを考えると、おそらく独自の最適化を行うことでメリットが得られます。これには、生のビットデータにアクセスできることが非常に重要です（たとえば、1バイト、またはメモリに余裕がある場合は2バイトのハミング重みの事前計算されたテーブルを使用します）。

私は一般的に車輪の再発明を提唱していません...しかし、特別な最適化要件がある場合は、それらに合わせてソリューションを調整するのが最善かもしれません。この場合、実装している機能は非常に単純です。

于 2012-09-18T02:11:54.983 に答える
1

数千ビットはそれほど多く聞こえません。しかし、多分あなたは何百万も持っています。

コードを抽象化して理想的な実装を作成した場合（最初はコーディングが簡単な実装を使用し、パフォーマンスやメモリ要件の問題を無視して）、いくつかの代替の特定の実装を試して（測定して）検証することをお勧めします。最高のパフォーマンスを発揮します。

考えもしなかった解決策の1つは、Judy配列（具体的にはJudy1配列）を使用することです。

于 2012-09-18T03:04:16.530 に答える
1

私があなただったら、おそらく DIY の手間を省き、boost::dynamic_bitsetを使用するだろうと思います。ファイル IO に使用できるストリーム演算子のオーバーロード (または単にデータをunsigned ints として読み取り、その変換を使用します。例を参照してください) やcountハミング重みのメソッドなど、機能面でカバーされているすべてのベースがあります。Boost は、少なくとも Sutter と Alexandrescu によって非常に高く評価されており、ヘッダー ファイルですべてを行います。リンクは行わず#include、適切なファイルのみを処理します。さらに、標準ライブラリとは異なり、bitset実行時まで待機してビ​​ットセットのサイズを指定できます。

編集：ブーストは、必要な高速入力読み取りを可能にしているようです。 dynamic_bitset次のコンストラクタを提供します。

template <typename BlockInputIterator>
dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
               const Allocator& alloc = Allocator());

基礎となるストレージは、s のstd::vector(またはそれとほとんど同じもの) です。したがって、ビットマップをofとして読み取ると、このコンストラクターはビットシフトせずに直接メモリに書き込みます。Blockuint64std::vectoruint64

于 2012-09-18T02:16:56.090 に答える