5

特定の操作について stl map と stl unordered_map を比較しようとしています。ネットで調べてみると、どれが全体的に優れているかという疑問が増すばかりです。そこで、両者が実行する操作に基づいて比較したいと思います。

どちらがより速く実行されますか

挿入、削除、検索

メモリからクリアするのに必要なメモリが少なく、時間が短いのはどれですか。どんな説明でも大歓迎です!!!

前もって感謝します

4

4 に答える 4

13

挿入、削除、ルックアップでパフォーマンスが速いのはどれですか？どちらがメモリからそれをクリアするのに必要なメモリと時間が少なくて済みます。説明は大歓迎です!!!

特定の用途については、実際のデータと使用パターンの両方を試して、どちらが実際に速いかを確認する必要があります...どちらかが常に「勝つ」と想定するのは危険な十分な要因があります。

順序付けされていないマップ/ハッシュテーブルの実装と特性

学術的に-要素の数が無限に向かって増加するにつれて、std::unordered_map（コンピューティングサイエンスが「ハッシュマップ」または「ハッシュテーブル」と呼ぶものを提供するC ++ライブラリである）に対するこれらの操作は、同じ時間かかる傾向がありますO （1）（メモリ制限/キャッシングなどを無視）、一方std::map（平衡二分木）では、要素の数が2倍になるたびに、通常、追加の比較操作を行う必要があるため、O（log 2 n ）。

std::unordered_map実装では必然的にオープンハッシュを使用します。基本的な期待は、「バケット」の連続した配列があり、それぞれが論理的にハッシュする値のコンテナであるということです。

これは通常、ハッシュテーブルをvector<list<pair<key,value>>>、ベクトル要素から値への取得に、バケットに格納されているリストヘッドポインターを最初のリストノードまでたどるときに、少なくとも1つのポインター逆参照が含まれる場所として描写するのに役立ちます。挿入/検索/削除操作のパフォーマンスは、リストのサイズに依存します。これは、平均してunordered_map'sに等しくなりload_factorます。

をmax_load_factor下げると（デフォルトは1.0）、衝突は少なくなりますが、挿入中の再割り当て/再ハッシュが増え、メモリの浪費が増えます（キャッシュミスの増加によりパフォーマンスが低下する可能性があります）。

この最も明白なunordered_map実装のメモリ使用量には、リストヘッドイテレータ/ポインタサイズのバケットの連続した配列と、bucket_count()キー/値ペアごとに1つの二重リンクリストノードの両方が含まれます。通常、bucket_count()+ 2 *size()オーバーヘッドの追加のポインターであり、実装が実行する可能性のある動的メモリ割り当て要求サイズの切り上げに合わせて調整されます。たとえば、100バイトを要求すると、128、256、または512になる可能性があります。実装の動的メモリルーチンは、割り当てられた/使用可能な領域を追跡するためにメモリを使用する場合もあります。

それでも、C ++標準は、実際の実装が独自のパフォーマンス/メモリ使用量の決定を行う余地を残しています。たとえば、新しい大きな配列を割り当てた後、バケットの古い連続配列をしばらく保持することができるため、後者への値の再ハッシュを徐々に実行して、平均的なパフォーマンスを犠牲にして、最悪の場合のパフォーマンスを減らすことができます。両方のアレイは、操作中に参照されます。

マップ/バランスの取れた二分木の実装と特性

Amapは二分木であり、へのさまざまな呼び出しによって返される個別のヒープメモリ領域をリンクするポインタを使用することが期待できますnew。キー/値データと同様に、ツリー内の各ノードには、親、左、および右のポインターが必要です（失われた場合は、ウィキペディアのバイナリツリーの記事を参照してください）。

比較

したがって、キー/値のペアにノードを割り当てる必要がunordered_mapありmapます。前者は通常、前/次のノードのリンケージに2つのポインター/イテレーターのオーバーヘッドがあり、後者は親/左/右に3つあります。ただし、unordered_mapさらにバケット用の単一の連続した割り当てがありますbucket_count()（== size()/ load_factor()）。

ほとんどの場合、これはメモリ使用量の劇的な違いではなく、1つの余分な領域の割り当て解除の時間差が目立つことはほとんどありません。

別の選択肢

コンテナが前もって入力され、それ以上挿入/消去せずに繰り返し検索される場合は、標準アルゴリズム、、、を使用して検索されたソート済みベクトルを使用するのが最も速い場合がbinary_searchあります。これには、単一の連続したメモリ割り当てという利点があり、キャッシュにはるかに適しています。常に優れていますが、それでも高速である可能性があります。気になる場合は測定してください。equal_rangelower_boundupper_boundmapunordered_map

于 2012-09-12T02:14:41.040 に答える
3

両方あるのは、全体としてどちらが優れているというわけではないからです。

どちらかを使用してください。他の方が使用に適していることが判明した場合は切り替えてください。

  • std::map は、悪い時間に対してより良いスペースを提供します。
  • std::unordered_map は、より悪いスペースに対してより良い時間を提供します。
于 2012-09-12T02:00:03.740 に答える
1

あなたの質問に対する答えは、使用している特定の STL 実装に大きく依存しています。本当に、STL 実装のドキュメントを確認する必要があります。おそらく、パフォーマンスに関するかなりの量の情報が含まれているはずです。

ただし、一般に、cppreference.com によると、マップは通常、赤黒木として実装され、時間計算量 O(log n) の操作をサポートしますが、unordered_mapsは通常、一定時間の操作をサポートします。cppreference.com では、メモリ使用量に関する洞察はほとんど提供されていません。ただし、別の StackOverflow の回答は、マップが一般的に unordered_maps よりも少ないメモリを使用することを示唆しています。

Visual Studio 2012 を使用した STL 実装 Microsoft パッケージの場合、mapは償却された O(log n) 時間でこれらの操作をサポートし、unordered_mapは償却された定数時間でそれらをサポートしているようです。ただし、ドキュメントには、メモリ フットプリントについて明示的な記述はありません。

于 2012-09-12T01:44:49.460 に答える
1

地図：

挿入：

  1. 最初のバージョン ( insert(x) ) の場合、対数。
  2. 2 番目のバージョン ( insert(position,x) ) では、一般に対数ですが、position が指す要素の直後に x が挿入された場合は償却定数です。
  3. 3 番目のバージョン ( insert (first,last) ) の場合、一般に Nlog(size+N) (N は first と last の間の距離、 size は挿入前のコンテナーのサイズ) ですが、要素間の要素が線形の場合は線形です。 first と last は、コンテナーで使用されているのと同じ順序付け基準に従って既に並べ替えられています。

消す：

  1. 最初のバージョン ( erase(position) ) の場合、償却定数。
  2. 2 番目のバージョン ( erase(x) ) の場合、コンテナー サイズは対数です。
  3. 最後のバージョン ( erase(first,last) ) の場合、コンテナー サイズの対数に加えて、first と last の間の距離の線形。

調べる：

  1. サイズは対数。

順序付けられていないマップ:

挿入：

  1. 単一要素の挿入:
    1. 平均的なケース: 一定。
    2. 最悪の場合: コンテナー サイズに比例します。
  2. 複数の要素の挿入:
    1. 平均的なケース: 挿入された要素の数に線形。
    2. 最悪の場合: N*(size+1): 挿入された要素の数 x コンテナー サイズ + 1。

消す：

  1. 平均的なケース: 削除された要素の数に線形 (要素を 1 つだけ削除した場合は一定)
  2. 最悪の場合: コンテナー サイズに比例します。

調べる：

  1. 平均的なケース: 一定。
  2. 最悪の場合: コンテナー サイズに比例します。

これらを知っていれば、実装のタイプに応じて使用するコンテナーを決定できます。

ソース: www.cplusplus.com

于 2012-09-13T15:34:26.823 に答える