461

C++に関する最近の話で、ルックアップの効率 (償却された O(1)対O(log n) ) のために、以前に使用したほとんどの場合にunordered_map使用する必要があることに気付きました。ほとんどの場合、マップを使用します。キー タイプとしてまたはを使用します。したがって、ハッシュ関数の定義に問題はありません。考えれば考えるほど、単純な型のキーの場合に a の上に aを使用する理由が見つからないことに気づきました。インターフェイスを調べたところ、何も見つかりませんでした。私のコードに影響を与える重要な違い。unordered_mapmapintstd::stringstd::mapstd::unordered_map

したがって、質問: andのような単純な型の場合にstd::mapoverを使用する本当の理由はありますか?std::unordered_mapintstd::string

私は厳密なプログラミングの観点から質問しています。それは完全には標準と見なされておらず、移植に問題を引き起こす可能性があることを知っています。

また、正しい答えの 1 つは、オーバーヘッドが小さいため、 「小さいデータ セットの方が効率的である」ということになると思います (それは本当ですか?)。 keys は自明ではありません (>1 024)。

編集： 当たり前のことを忘れていました（GManに感謝します！）-はい、もちろんマップは順序付けられています-私はそれを知っており、他の理由を探しています。

4

15 に答える 15

483

map要素の順序を維持することを忘れないでください。それを諦められないなら、当然使えませんunordered_map。

心に留めておくべきもう1つのことは、unordered_map一般的により多くのメモリを使用することです。mapいくつかのハウスキーピング ポインターと、各オブジェクトのメモリがあります。反対にunordered_map、大きな配列 (これらは一部の実装では非常に大きくなる可能性があります) を持ち、オブジェクトごとに追加のメモリを持ちます。メモリを意識する必要がある場合mapは、大きな配列がないため、より良いことが証明されるはずです。

したがって、純粋なルックアップ検索が必要な場合は、それが道だと思いますunordered_map。しかし、常にトレードオフがあり、それらを買う余裕がなければ、それを使用することはできません.

個人的な経験から、メイン エンティティ ルックアップ テーブルのunordered_map代わりにを使用すると、パフォーマンスが大幅に向上することがわかりました (もちろん、測定されています)。map

一方、要素の挿入と削除を繰り返すと、はるかに遅くなることがわかりました。要素の比較的静的なコレクションには最適ですが、大量の挿入と削除を行っている場合は、ハッシュとバケット化が加算されるようです. (注、これは何度も繰り返されました。)

于 2010-02-04T02:43:15.440 に答える
145

あなたの実装std::mapとstd::unordered_map実装の速度を比較したい場合は、time_hash_map プログラムを含む Google のsparsehashプロジェクトを使用して時間を計ることができます。たとえば、x86_64 Linux システムで gcc 4.4.2 を使用すると、

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)
于 2010-10-22T18:38:34.007 に答える
93

GMan が行ったのとほぼ同じポイントを繰り返します。使用の種類によっては、(VS 2008 SP1 に含まれる実装を使用してstd::map) よりも高速になる可能性があります (多くの場合はそうです)。std::tr1::unordered_map

覚えておくべきいくつかの複雑な要因があります。たとえば、 ではstd::map、キーを比較しています。つまり、ツリーの右サブブランチと左サブブランチを区別するのに十分なキーの先頭だけを調べます。私の経験では、キー全体を見るのは、単一の命令で比較できる int のようなものを使用している場合だけです。std::string のようなより一般的なキー タイプでは、数文字程度しか比較しないことがよくあります。

対照的に、適切なハッシュ関数は常にキー全体を調べます。IOW、テーブル ルックアップが一定の複雑さであっても、ハッシュ自体はおおよそ線形の複雑さを持ちます (アイテムの数ではなく、キーの長さではありますが)。長い文字列をキーとして使用すると、が検索を開始std::mapする前に が検索を終了する可能性がありunordered_mapます。

第 2 に、ハッシュ テーブルのサイズを変更する方法はいくつかありますが、それらのほとんどは非常に遅く、検索が挿入や削除よりもかなりstd::unordered_map頻繁に行われない限り、std::map は多くの場合よりも高速になります。

もちろん、前の質問のコメントで述べたように、ツリーのテーブルを使用することもできます。これには、長所と短所の両方があります。一方では、最悪のケースをツリーのケースに限定します。また、（少なくとも私が行ったときは）固定サイズのテーブルを使用したため、挿入と削除を高速に行うことができます。テーブルのサイズ変更をすべて排除することで、ハッシュ テーブルをよりシンプルに、通常は高速に保つことができます。

もう 1 つのポイント: ハッシュとツリーベースのマップの要件は異なります。ハッシュには明らかにハッシュ関数と等値比較が必要ですが、順序付けられたマップにはより少ない比較が必要です。もちろん、前述のハイブリッドには両方が必要です。もちろん、文字列をキーとして使用する一般的なケースでは、これは実際には問題になりませんが、一部のタイプのキーは、ハッシュよりも順序付けに適しています (またはその逆)。

于 2010-02-04T05:15:55.953 に答える
67

@Jerry Coffin からの回答に興味をそそられました。これは、順序付けられたマップが長い文字列でパフォーマンスの向上を示すことを示唆していました。いくつかの実験 (これは pastebin からダウンロードできます)の後、これはコレクションにのみ当てはまるように思われることがわかりました。ランダムな文字列の場合、マップがソートされた辞書 (かなりの量のプレフィックスの重複がある単語を含む) で初期化されると、おそらく値を取得するために必要なツリーの深さが増加するため、このルールは破られます。結果を以下に示します。最初の数値列は挿入時間、2 番目の列はフェッチ時間です。

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298
于 2012-09-20T11:56:41.073 に答える
39

ここでは十分に言及されていない重要な違い:

  • mapすべての要素へのイテレータを安定に保ちます。C++17 では、要素へのイテレータを無効にすることなく要素をある要素から別の要素に移動することさえできmapます (潜在的な割り当てなしで適切に実装されている場合)。
  • map単一の操作のタイミングは、大規模な割り当てを必要としないため、通常、より一貫しています。
  • unordered_maplibstdc++ に実装されているものを使用std::hashすると、信頼できない入力が与えられた場合に DoS に対して脆弱になります (一定のシードを持つ MurmurHash2 を使用します。シードが実際に役立つわけではありません。https://emboss.github.io/blog/2012/12/14/ を参照してください)。速報つぶやきハッシュフラッディング-dos-reloaded/ )。
  • 順序付けを行うと、効率的な範囲検索が可能になります。たとえば、キーが 42 以上のすべての要素を反復処理できます。
于 2016-12-29T16:57:24.633 に答える
31

ただ指摘したいのは... には多くの種類があるということですunordered_map。

ハッシュ マップに関するウィキペディアの記事を参照してください。使用された実装に応じて、ルックアップ、挿入、および削除に関する特性が大幅に異なる場合があります。

そして、それがSTLへの追加で私が最も心配していることですunordered_map。彼らは特定の実装を選択する必要がありますPolicy.他のケース...

たとえば、一部のハッシュ マップには線形再ハッシュがあり、ハッシュ マップ全体を一度に再ハッシュするのではなく、挿入ごとに一部を再ハッシュするため、コストの償却に役立ちます。

別の例: 一部のハッシュ マップはバケットのノードの単純なリストを使用し、他のハッシュ マップはマップを使用し、他のものはノードを使用せずに最も近いスロットを見つけ、最後にいくつかはノードのリストを使用しますが、最後にアクセスされた要素がは前面にあります (キャッシングのように)。

したがって、現時点では、std::mapまたはおそらく a loki::AssocVector(凍結されたデータセットの場合) を好む傾向があります。

誤解しないでいただきたいのですが、std::unordered_map私は将来的に を使用したいと考えていますが、そのようなコンテナーの移植性を「信頼」するのは、それを実装するすべての方法とその結果として得られるさまざまなパフォーマンスを考えると難しいことです。これの。

于 2010-02-04T07:59:02.267 に答える
20

理由は他の回答で与えられています。ここに別のものがあります。

std::map (平衡二分木) 操作は、O(log n) と最悪の場合 O(log n) に償却されます。std::unordered_map (ハッシュテーブル) 操作は償却された O(1) および最悪の場合の O(n) です。

これが実際にどのように機能するかというと、ハッシュ テーブルが時々 O(n) 操作で "しゃっくり" するということです。許容できない場合は、std::unordered_map よりも std::map を使用することをお勧めします。

于 2016-10-05T03:02:56.093 に答える
15

ハッシュ テーブルには、一般的なマップの実装よりも高い定数があり、小さなコンテナーでは重要になります。最大サイズは 10、100、または 1,000 以上ですか? 定数はこれまでと同じですが、O(log n) は O(k) に近くなっています。(対数の複雑さは依然として非常に優れていることを思い出してください。 )

優れたハッシュ関数の条件は、データの特性によって異なります。したがって、カスタム ハッシュ関数を検討する予定がない場合 (ただし、後で気が変わることは確かです。ほとんどすべてのデータを typedef で処理しているため、簡単に変更できます)、多くのデータ ソースに対して適切に機能するように既定値が選択されているにもかかわらず、順序付けされていることがわかります。マップの性質は、最初は十分な助けになるため、その場合はハッシュテーブルではなくデフォルトでマップします。

さらに、その方法では、他の (通常は UDT) 型のハッシュ関数を書くことを考える必要さえなく、op< と書くだけです (とにかく必要です)。

于 2010-02-04T02:52:02.883 に答える
10

最近、50000 件のマージとソートを行うテストを行いました。つまり、文字列キーが同じ場合、バイト文字列をマージします。そして、最終出力はソートする必要があります。したがって、これにはすべての挿入のルックアップが含まれます。

実装ではmap、ジョブを完了するのに 200 ミリ秒かかります。unordered_map+の場合、挿入に 70 ミリ秒、挿入に 80 ミリmap秒かかります。したがって、ハイブリッド実装は 50 ミリ秒高速です。unordered_mapmap

を使用する前によく考えてくださいmap。プログラムの最終結果でデータを並べ替えるだけでよい場合は、ハイブリッド ソリューションの方が適している場合があります。

于 2013-03-11T03:32:36.330 に答える
-1

出典：http ://www.cplusplus.com/reference/map/map/

内部的には、マップ内の要素は常に、その内部比較オブジェクト (Compare 型) によって示される特定の厳密な弱い順序付け基準に従って、そのキーによって並べ替えられます。

マップ コンテナーは一般に unordered_map コンテナーよりもキーによって個々の要素にアクセスするのに時間がかかりますが、順序に基づいてサブセットを直接反復できます。"

于 2016-09-03T16:14:10.630 に答える