以下に使用するデータ構造を決定しようとしています。
いくつかのデータを含む一意のオブジェクトへのポインターを含むキーが 1,000 万個あるとします。
キーは UUID の 16 バイトのバイナリ配列と見なされます。UUID は、高品質の乱数ジェネレーターを使用して生成されます。
以下を検討していますが、それぞれの速度とメモリ消費の長所と短所を知りたいです。いくつかの公正な見積もり、64 ビット プラットフォームでの最良/最悪/平均のケースが適切です。
事実上無制限のアイテムを挿入できるようにする必要があります。
バイナリ ツリー ハッシュ テーブル 基数ツリー (ビット ベースまたは 2 ビット マルチウェイ)
これらに必要な操作は、挿入、削除、検索です
基数ツリーのアイデアは気に入っていますが、実装が最も難しいことが判明しており、商用製品に組み込むことができる適切な実装が見つかりませんでした。
短い答え
あなたのケースにはおそらくハッシュテーブルが最適でしょう。
スピード
ハッシュが定数の場合、ハッシュ テーブル ( std::unordered_map) はO ( 1 ) になります。あなたの場合、ハッシュする必要さえないため、 O ( 1 ) が保持されます。ランダムな UUID の下位 32 ビットを使用するだけで十分です。ルックアップのコストは、1 つまたは 2 つのポインター インダイレクションに似ています。
二分木 ( std::map) はO ( log 2 n ) になるため、1,000 万個のアイテムの場合、24 回の比較と 24 回の潜在的なキャッシュ ミスが発生します。n = 4,000の場合でも12 回の比較を使用するため、すぐにハッシュ テーブルよりも大幅に悪化します。
基数ツリーはO ( k ) になるため、最大k 個の比較とk 個の潜在的なキャッシュ ミスが発生します。最悪の場合、基数ツリーはハッシュ テーブルと同じくらい高速になります。最悪の場合 (256 方向のツリーの場合、 k = ある程度妥当な 16 であると仮定)、バイナリ ツリーよりも優れたパフォーマンスを発揮しますが、ハッシュ テーブルよりもはるかに劣ります。
したがって、速度が最優先される場合は、ハッシュ テーブルを使用してください。
オーバーヘッド
典型的なハッシュ テーブルは、いっぱいになった場合、項目ごとに約 1 ～ 3 個のポインターのオーバーヘッドがあります。いっぱいでない場合は、空のスロットごとに 1 ポインターのスペースを浪費することになるでしょう。非常にランダムなキーを持っているため、バイナリツリーよりも高速でありながら、ほぼ完全に保つことができるはずですが、可能な限り最大の速度を得るには、もちろん十分なヘッドルームを与える必要があります. 32 ビット マシンで 1,000 万項目の場合、テーブル全体で 38 ～ 114MiB のオーバーヘッドが予想されます。テーブルが半分埋まっている場合は、76 ～ 153 MiB が予想されます。
最も一般的な実装である赤黒ツリーには、std::mapアイテムごとに 3 つのポインター + 1 つのブール値があります。一部の実装では、ポインターの配置を利用して、bool をポインターの 1 つとマージします。実装とハッシュ テーブルがどれだけいっぱいかによっては、赤黒ツリーのオーバーヘッドがわずかに低くなる場合があります。114–153MiB を期待してください。
基数ツリーには、アイテムごとに 1 つのポインターと、空のスロットごとに 1 つのポインターがあります。残念ながら、このような大きなランダム キーを使用すると、ツリーの端に向かって空のスロットが非常に多くなり、おそらく上記のいずれよりも多くのメモリを使用することになると思います。kを小さくすると、このオーバーヘッドを下げることができますが、同様にパフォーマンスが低下します。
最小限のオーバーヘッドが重要な場合は、ハッシュ テーブルまたはバイナリ ツリーを使用します。優先度が高い場合は、完全なハッシュ テーブルを使用します。
std::unordered_mapサイズを変更するタイミングを制御できないため、完全に取得するのは難しいことに 注意してください。Boost Intrusiveunordered_mapには、それや他の多くのことを直接制御できる非常に優れた実装があります。
私は最初にしようとしstd::mapますstd::unordered_map。
彼らは何年にもわたって多くの賢い人々を開発し、改善してきました。
使えない理由はありますstd::mapかstd::unordered_map？
簡単な計算をしたところ、標準的なツリーで問題ないと思います。1000 万キーは妥当な数です。チェックするノードが 23 のみの深さになるバランスの取れたツリーを使用します。基数ツリーを使用すると、実際には 128 バイトのキーの長さをチェックする必要があります。
あなたのキーは、非常に安価に表現および比較することもできます。2 つの 64 ビット値のタプル (ブーストまたは 0x) を使用して、同じ 128 ビット キーを取得します。タプルの順序付けは、マップで使用するのに十分です。したがって、比較と同様に、キーのコピーは安価です。整数をそのまま比較する方が、基数深度検索でマスキングやビットベースの比較を行うよりもコストがかからない可能性があります。
したがって、この場合、マップは問題なく機能する可能性があります。
* unordered_mapUUID は構造化データである傾向があるため、ここでは避けます。これは、標準のハッシュ手順 (ハッシュ マップの場合) のパフォーマンスが非常に低下する可能性があることを意味します。*
アップデート：
ランダムな UUID を使用しているため、ハッシュは問題ないかもしれませんが、そのような大きなハッシュ テーブルには、効率を維持するためのかなりのメモリ オーバーヘッドがあります。
また、完全にランダムな UUID を指定すると、基数はツリーと同じバランスになる可能性があります (キーの配布が完全に均等であるため)。したがって、ステップを節約できず、ビット操作のオーバーヘッドが発生する可能性があります。しかし、基数ツリーを特殊化して最適化する方法は非常に多いため、より高速になるか、常に低速になるかを明確に言うのは困難です。
IMO 基数ツリーの実装は難しくありません。ただし、単純なハッシュ テーブルで十分です。オブジェクトの 2^16 リストの配列を割り当て、UUID の最初の 2 バイトを使用して、オブジェクトを挿入するリストのインデックスを作成します。その後、約160項目のリストを検索できます。
または、20M ポインターの配列を割り当てます。オブジェクトを保存するには、UUID のハッシュを 0 ～ 20M の範囲で作成し、最初の空き (NULL) ポインターを見つけてそこに保存します。検索とは、ハッシュ値から最初の NULL 値まで歩くことを意味します。削除も簡単です....読んでみてくださいhttp://en.wikipedia.org/wiki/Hash_function