10

繰り返されない要素をSTLコンテナに追加する最も効率的な方法は何ですか？また、どの種類のコンテナが最も高速ですか？大量のデータがあり、新しい要素かどうかを確認するたびに時間がかかるのではないかと思います。マップが非常に高速であることを願っています。

// 1- Map
map<int, int> Map;
...
if(Map.find(Element)!=Map.end()) Map[Element]=ID;

// 2-Vector
vector<int> Vec;
...
if(find(Vec.begin(), Vec.end(), Element)!=Vec.end()) Vec.push_back(Element);

// 3-Set
// Edit: I made a mistake: set::find is O(LogN) not O(N)
4

6 に答える 6

19

両方ともset、キーを検索するためのパフォーマンスがmapあります。持っています。O(log(N))vectorO(N)

setとの違いはmap、あなたが懸念している限り、キーを値に関連付ける必要があるのか​​、それとも単に値を直接格納する必要があるのか​​ということです。前者が必要な場合は、を使用しmap、後者が必要な場合は、を使用しsetます。

どちらの場合も、を実行するinsert()代わりにを使用する必要がありますfind()。

その理由はinsert()、コンテナにその値がまだ含まれていない場合にのみ（mapコンテナにそのキーが含まれていない場合）、値をコンテナに挿入するためです。これは次のようになります

Map.insert(std::make_pair(Element, ID));

地図または

Set.insert(Element);

セットのために。

戻り値を調べて、挿入が実際に実行されたかどうかを判断できます。

C ++ 11を使用している場合は、さらに2つの選択肢があります。それはstd::unordered_mapとstd::unordered_setです。O(1)これらは両方とも、挿入とルックアップのパフォーマンスを償却しています。ただし、キー（またはセットの場合は値）がハッシュ可能である必要もあります。つまり、std::hash<>キーに特化する必要があります。逆に、キー（またはセットの場合は値）がに応答することを要求しstd::mapます。std::setoperator<()

于 2013-01-22T23:15:19.510 に答える
7

C++11 を使用している場合は、std::unordered_set. これにより、O(1)存在チェックが可能になります（技術的には償却されますO(1)-O(n)最悪の場合）。

std::setはおそらく の 2 番目の選択肢O(lg n)です。

基本的にstd::unordered_setは、ハッシュ テーブルでstd::setあり、ツリー構造です (これまでに見たすべての実装で赤黒のツリー) 1 .

ハッシュがどれだけうまく分散されているか、およびアイテムの数によっては、std::set の方が実際には高速である可能性があります。本当にパフォーマンスが重要な場合は、いつものように、ベンチマークを実行する必要があります。

1）技術的に言えば、ハッシュテーブルまたはバランスの取れたBSTとして実装する必要があるとは思いません。私の記憶が正しければ、標準は実装ではなく実行時間の境界を義務付けているだけです。境界に適合する唯一の実行可能な実装であることが判明しただけです。

于 2013-01-22T23:15:37.960 に答える
3

std::set;を使用する必要があります。これは、オブジェクトの 1 つの (同等の) コピーを保持するように設計されたコンテナーであり、二分探索ツリーとして実装されます。そのため、容器のサイズではO(log N)ありません。O(N)

std::set多くの場合、基礎とstd::mapなる実装の大部分を共有します。ローカルの STL 実装をチェックアウトする必要があります。

とはいえ、複雑さはパフォーマンスの指標の 1 つにすぎません。並べ替えられたベクトルを使用すると、データが互いにローカルに保持されるため、パフォーマンスが向上する可能性があります。したがって、キャッシュにヒットする可能性が高くなります。キャッシュの一貫性は、最近のデータ構造設計の大部分を占めています。

于 2013-01-22T23:15:19.177 に答える
1

を使用したいようですねstd::set。その要素は一意であるため、要素を追加するときに一意性を気にする必要はありません。また、a.find(k)( は でaありstd::set、kは値です) は、複雑さが対数的であると定義されています。

于 2013-01-22T23:15:34.200 に答える
1

要素を O(1) でハッシュできる場合は、unordered_mapまたはでインデックスを使用することをお勧めします (O(logN) である実装で RB ツリーを使用するため、 /unordered_setではなく複雑さを見つけます)。mapset

于 2013-01-22T23:16:19.040 に答える
1

あなたの例は明確なパターンを示しています：

check if the value is already in container
  if not, add the value to the container.

これらの操作はいずれも時間がかかる可能性があります。まず、要素の検索は、要素が特定の方法で配置されていない場合 (線形検索) std::vector、O(logN) 時間 (バイナリ検索) で実行できます。 ) 要素がソートされている場合 (たとえば、 または のいずれstd::mapか)、要素がハッシュされている場合 (たとえば、 または のいずれかstd::set) は O(1) 時間で実行できます。std::unordered_mapstd::unordered_set

プレーンなベクターまたは順序付けされていないコンテナー (ハッシュ コンテナー) の場合、挿入は O(1) (償却) になりますが、ハッシュ コンテナーは少し遅くなります。set や map などの並べ替えられたコンテナーの場合、挿入する前に挿入する場所を探す必要があるため、ログ時間の挿入が発生します。

したがって、結論として、std::unordered_setor std::unordered_map(キー値機能が必要な場合) を使用します。また、挿入を行う前に確認する必要はありません。これらは一意のキー コンテナーであり、重複は許可されません。

std::unordered_set/ std::unordered_map(C++11 から) またはstd::tr1::unordered_set/ (2007 年以降) が利用できない場合std::tr1::unordered_map(または同等のもの)、次善の策はstd::set/std::mapです。

于 2013-01-22T23:25:39.873 に答える