vs2005 サポート ::stdext::hash_map ::std::map。
ただし、 ::stdext::hash_map の挿入および削除 OP は、私のテストでは ::std::map よりも遅いようです。( 10000 アイテム未満)
面白い....
それらについての比較記事を提供できる人はいますか?
15426 次
6 に答える
9
通常、さまざまな操作の複雑さに目を向けます。これは良いガイドです。償却された O(1) 挿入、O(1) ルックアップ、ハッシュマップの削除に対して、ツリーの O(log N) 挿入、ルックアップ、削除-ベースマップ。
ただし、含まれる定数項が極端であるため、複雑さが誤解を招く特定の状況があります。たとえば、10,000 個のアイテムが文字列から切り離されているとします。さらに、これらの文字列がそれぞれ 10 万文字の長さであるとします。異なる文字列は通常、文字列の先頭付近で異なるとします (たとえば、それらが本質的にランダムである場合、ペアは最初のバイトで 255/256 の確率で異なります)。
次に、ルックアップを行うために、ハッシュマップは 100k 文字列をハッシュする必要があります。これはコレクションのサイズでは O(1) ですが、文字列の長さではおそらく O(M) であるため、かなり時間がかかる場合があります。バランスの取れたツリーでは、log N <= 14 の比較を行う必要がありますが、各比較は数バイトしか確認する必要がありません。これにはそれほど時間がかからないかもしれません。
メモリ アクセスに関しては、キャッシュ ライン サイズが 64 バイトの場合、ハッシュマップは 1500 を超える順次ラインをロードし、100k バイトの操作を実行しますが、ツリーは 15 のランダム ラインをロードし (実際には文字列の間接化によりおそらく 30 行)、14 を実行します。 * (少数の) バイト操作。前者は後者よりも遅い可能性があることがわかります。または、より高速な場合もあります。アーキテクチャの FSB 帯域幅、ストール時間、投機的読み取りキャッシュはどれくらい優れていますか?
ルックアップで一致が見つかった場合は、もちろん、これに加えて、両方の構造で完全な長さの文字列を 1 回比較する必要があります。また、バケット内で衝突が発生した場合、ハッシュマップは追加の失敗した比較を行う可能性があります。
したがって、失敗した比較が無視できるほど高速であると仮定すると、成功した比較とハッシュ操作は低速ですが、ツリーはハッシュの約 1.5 倍から 2 倍高速になる可能性があります。それらの仮定が成り立たない場合、それは成り立ちません。
もちろん極端な例ですが、データでは、特定の O(log N) 操作が特定の O(1) 操作よりもかなり高速である可能性があることは簡単にわかります。もちろん、テストしたいのは当然ですが、テスト データが現実世界を代表していない場合、テスト結果も代表的ではない可能性があります。複雑さに基づくデータ構造の比較は、N が無限に近づくときの極限での動作を参照します。しかし、N は無限大には近づきません。10000です。
于 2009-07-14T11:12:54.227 に答える
6
挿入と削除だけではありません。hash_map と map ではメモリの割り当てが異なり、検索される値のハッシュを毎回計算する必要があることを考慮する必要があります。
このDr.Dobbsの記事があなたの質問に最もよく答えると思います:
于 2009-07-14T10:24:53.170 に答える
2
それは、使用法とハッシュの衝突によって異なります。1 つは二分木で、もう 1 つはハッシュテーブルです。
理想的には、ハッシュ マップは O(1) の挿入とルックアップ、およびマップ O(ln n) を持ちますが、衝突しないハッシュを想定しています。
于 2009-07-14T10:02:28.567 に答える
2
hash_mapはhash tableを使用します。これは、適切なハッシュ関数を想定して、ほぼ一定時間の O(1) 操作を提供するものです。
mapはBSTを使用し、O(lg(n)) 操作を提供します。これは 13 である 10000 要素に対して非常に受け入れられます。
地図を持っていた方が安全だと思います。
于 2009-07-14T14:26:04.433 に答える
0
ハッシュ マップは、インデックス作成用の文字列/キーのハッシュを作成します。複雑さを証明しながら O(1) として言及されていますが、文字列のハッシュは別の文字列のハッシュと同じインデックスを生成できるため、hash_map はすべての挿入に対して衝突検出を行います。したがって、ハッシュマップにはこれらの衝突を管理するための複雑さがあり、これらの衝突は入力データに基づいていることがわかります。
ただし、構造体で多くのルックアップを実行する場合は、hash_map を選択してください。
于 2009-07-14T10:09:42.873 に答える
0
ハッシュ テーブルは、ルックアップの場合、バイナリ ツリー (つまり、std::map) よりも高速であると想定されています。挿入と削除が高速であると示唆した人は誰もいません。
于 2009-07-14T10:06:37.793 に答える