操作が 2 つだけの高速コンテナーが必要です。非常にまばらなドメイン (すべての 32 ビット整数、および約 100 個が一度に設定される) からキーを挿入し、挿入されたキーを反復処理します。同じエントリにヒットする多くの挿入を処理する必要があります (500k のように、しかし 100 の異なるエントリのみ)。
現在、私は std::set (挿入と反復インターフェイスのみ) を使用しています。これは適切ですが、まだ十分に高速ではありません。std::unordered_set は、Google Hash Maps と同じように 2 倍遅くなりました。この場合、どのデータ構造が最適化されているのだろうか?
入力の分布によっては、構造を変更せずに改善できる場合があります。
単一の値を何度も取得する傾向がある場合は、最後に挿入した値の記録を保持することで挿入を高速化でき、一致する場合はわざわざ挿入する必要はありません。入力ごとに追加の比較が必要ですが、最初の実行以降の実行で各要素のルックアップが保存されます。したがって、繰り返しの頻度と比較と挿入の相対的なコストに応じて、使用しているデータ構造に関係なく、物事を改善できます。
ランが得られなくても、値が均等に分散されていない傾向がある場合は、スプレイ ツリーを使用すると、最も一般的に使用される要素へのアクセスが安価になります。これは、ハフマン コードのように、頻繁に使用される要素を上部に配置して、意図的に不均衡なツリーを作成することによって機能します。
「同じエントリにヒットする多くの挿入」を理解しているかどうかはわかりません。メンバーである値は 100 個しかなく、それらの 100 個の値の 1 つを挿入する 500k のほとんど重複した操作があるということですか?
もしそうなら、最速のコンテナは、それらの100個の値に対して衝突のないハッシュを生成し、フラグの配列（またはベクトル）を維持することであると思います（intまたはbit、アーキテクチャで最も速く動作するものに応じて） ）。
ハッシュの生成は、技術として存在することを知っているため、読者の演習として残しますが、自分で調べたことはありません。ポイントは、100 個の値の各 n、m について、hash(n) != hash(m) のように、できるだけ狭い範囲で高速なハッシュを取得することです。
したがって、挿入は のように見えarray[hash(value)] = 1;、削除はarray[hash(value)] = 0;(必要ありませんが) のように見え、配列を列挙するには、インデックス n の設定値ごとに inverse_hash(n) がコレクションにあります。範囲が狭い場合は、ルックアップ テーブルを簡単に維持して逆ハッシュを実行できます。または、配列全体をスキャンしてフラグの設定を探す代わりに、100 個の潜在的な値を実行して、それぞれを順番にチェックすることができます。
状況を誤解していて、これが役に立たない場合は申し訳ありません。正直なところ、通常のハッシュテーブルよりもはるかに高速というわけではありません。実際には、100 個の値の場合、キャッシュを吹き飛ばすほど多くのメモリを使用することなく、衝突がほとんどまたはまったくないようにテーブルのサイズを簡単に変更できるからです。
これほど小さいと予想される使用中のセットの場合、バケット化されていないハッシュテーブルで問題ない可能性があります。たまに拡張操作を行うことができる場合は、70％を超えていっぱいになったら、2の累乗で成長させます。 カッコウのハッシュは以前にStackoverflowで説明されており、これほど小さなセットには良いアプローチかもしれません。本当に速度を最適化する必要がある場合は、ハッシュ関数とルックアップをアセンブラーで実装できます。線形データ構造では、これは非常に簡単なので、アセンブラー実装のコーディングとメンテナンスの労力を過度に維持するのは難しいことではありません。
バイナリ ハッシュ関数の代わりに、各レベルで基数 10 のハッシュ関数を使用してHashTreeを実装することを検討することをお勧めします。バケット化しないようにすることもできます。その場合、パフォーマンスは決定論的 (log10) になるか、予想される分布に基づいてバケット サイズを調整して、キー/バケットが 2 つだけになるようにします。
ランダム化されたデータ構造は、あなたの仕事に最適かもしれません。スキップ リストを見てみましょう。ただし、その適切な C++ 実装については知りません。Boost に投稿するつもりでしたが、実行できませんでした。
ハッシュ テーブルへの挿入は高速ですが、配列全体を反復処理する必要があるため、反復処理は特に高速ではないことに注意してください。
どの操作が遅いですか? より多くの挿入またはより多くの反復を行いますか?
どのくらいのメモリを持っていますか? 32 ビットは 4GB/8 バイト「のみ」しか必要とせず、これは 512MB になり、ハイエンド サーバーにはあまり多くありません。これにより、挿入が O(1) になります。しかし、それは反復を遅くする可能性があります。ただし、ゼロのみのすべての単語をスキップすると、ほとんどの反復が最適化されます。100 個の数値が比較的小さい範囲にある場合は、最小値と最大値を維持することでさらに最適化できます。
これが単なる力ずくであることはわかっていますが、力ずくで十分な場合もあります。
誰も明示的に言及していないので、メモリの局所性について考えたことはありますか? ページ フォールトを引き起こす挿入アルゴリズムを備えた非常に優れたデータ構造は、何の役にも立たないでしょう。実際、単にキャッシュ ミスを引き起こすだけの挿入を伴うデータ構造は、パフォーマンスにとって非常に悪いものになる可能性があります。
挿入の衝突が遅すぎるときに単純な前へのスワップを使用して、固定配列にパックされた単純な順序付けられていない要素のセットを確認しましたか? アルゴリズムの問題ではなく、メモリの局所性の問題があることを示す簡単な実験です。