3

1つの巨大なメモリブロックに格納されている文字列の大きなリストがあります（通常、10万以上または100万以上の文字列があります）。これらは実際にはハッシュであるため、文字列のアルファベットはA-F0-9に制限され、各文字列の長さは正確に32バイトです（したがって、格納されている「圧縮」）。これからこのリストをメインリストと呼びます。

メインリストからアイテムを削除できるようにしたい。これは通常一括で行われるため、このリストで見つけて削除する必要のあるハッシュの大きなリスト（通常は約10万から10k）を取得します。この操作の最後に、大きなメモリブロックに空のブロックを含めることはできないため、それを考慮する必要があります。すべてのアイテムがメインリストに含まれることは保証されていませんが、複数回含まれることはありません。再配置はできません。メインブロックは常に同じサイズのままです。

メインリストを反復処理し、指定されたハッシュを削除するかどうかを確認するという単純なアプローチはもちろん機能しますが、少し時間がかかります。また、ハッシュに削除のフラグが立てられるたびに、メインリストの最後の要素でハッシュを書き換えて、空のブロックがないという条件を満たすため、小さなメモリブロックの移動が少し多すぎます。もちろん、これにより何千もの小さなmemcpyが作成され、キャッシュミスが大量に発生するため、処理速度がさらに低下します。

より良いアプローチはありますか？

いくつかの重要な注意事項：

  • メインリストは並べ替えられておらず、並べ替えに時間を無駄にすることはできません。これはプロジェクト全体と書き換えによって課せられる制限であるため、リストを常に並べ替えることはできません（不可能な場合もあります）。
  • メモリは実際には問題ではありませんが、使用量が少ないほど良いです
  • STLは使用できますが、ブーストはできません
4

2 に答える 2

2

さて、これから私が絶対に地獄を最適化する必要があった場合、これが私がすることです。順序は関係ないと思います。これは、あなた（IIUC）がアイテムを最後のアイテムと交換して削除する場合のようです。

  • 32文字の文字列の代わりに128ビット整数を格納します（ただし、それらを表現する場合は、コンパイラがそれらをネイティブにサポートするか、32/64ビット整数の小さな配列を使用します）。質問に対する私のコメントを参照してください。
  • 128ビット整数の独自のハッシュセットをロールします。少し考えて、いくつかの仮定を立てて、汚れた状態に陥る気がある場合は、ここで多くのことを最適化できることに注意してください。いくつかのメモ：
    • ハッシュ自体（衝突解決のため）と、削除された/未使用のスロットを識別するためのメタデータを少しだけ保存する必要があります。正確さを保証する方法がわからない場合は、既存のハッシュテーブルが何をするかを見てください。ハッシュセットを作成した後でのみ削除（追加ではない）すると、さらに簡単になると思います。空のスロットを示す有効なハッシュではない値がある場合は、そのメタデータがなくても実行できると思いますが、この方法の方が簡単です（128ビットを上書きするのではなく、ビットを反転するだけです）。
    • 入力はすでに整数であるため、ハッシュ関数は必要ありません。とにかく、すべてのハッシュテーブルが行うことを実行する必要があります。2^ nを法とするハッシュを使用して、巨大ではないインデックスを導出します。負荷率（使用されるテーブルエントリのパーセンテージ）が妥当であるようにnを選択します（<2/3が標準のようです）。の累乗を選択すると、モジュロ演算が安価になり（バイナリANDを介してビットをマスクオフ）、下位32ビットまたは64ビットで実行できるようになります（残りは無視されます）。
    • 衝突解決戦略を選択するのは難しいです。私はおそらく、最初の試みとして、線形プロービングを使用したオープンアドレッシングを使用します。うまく機能しない可能性がありますが、入力ハッシュが適切であれば、これはありそうにないようです。CPythondictで使用されている、最初に切り取ったビットをますます多く考慮に入れるプロービングスキームもあります。

現在、これは既製のソリューションを使用するよりもはるかに多くの作業とメンテナンスの負担です。これがあなたの説明で聞こえるほどパフォーマンスに重要である場合を除いて、私はそれをお勧めしません。C ++ 11がオプションであり、コンパイラunordered_setが優れている場合は、C ++ 11を使用するだけで、面倒な作業をほとんど省くことができます（ただし、これによりメモリ要件が増える可能性があることに注意してください）。あなたはまだ専門化する必要がありますstd::hashそしてstd::equal_toまたはoperator==。代わりにあなた自身HashとKeyEqualのために供給してくださいunordered_set、しかしそれはおそらく何の利益も提供しません。

于 2013-02-11T15:44:30.813 に答える
1

2つのことが役立つかもしれません。まず、少なくとも削除するアイテムのリストを並べ替えます。そうすれば、二分探索（std::lower_bounds）を使用できます。次に、ソースと宛先の2つのポインターを保持します。ソースが削除するリストにないものを指している場合は、それを宛先にコピーして、両方を進めます。ソースが削除するものを指している場合は、コピーせずにソースポインタを進めるだけです。エントリを複数回コピーする理由はありません。

于 2013-02-11T15:31:22.773 に答える