私は現在、vectorのを使用しているいくつかのコードを持っていますpair<string,string>。これは、XML解析からの一部のデータを格納するために使用されるため、場所によってはプロセスが非常に遅くなります。vector<pair<string,string> >プロセス全体を高速化するという点で、からに切り替えることでパフォーマンス上の利点があるかどうか疑問に思いましたstd::map<string,string>。コード化してプロファイラーを実行することはできましたが、最初に明らかなパフォーマンスの向上を示唆する答えが得られるかどうかを確認したいと思いました。並べ替えを行う必要はありません。ベクターにアイテムを追加するだけで、後の段階でコンテンツを繰り返し処理して処理を行うだけです。並べ替えなどの必要はありません。おそらくパフォーマンスが向上しないと思いますが、実際に使用したことはありません。std::map以前は、すべてを尋ねたりコーディングしたりしなければわかりません。
3028 次
5 に答える
11
いいえ。（あなたが言うように）単にコレクションを反復処理している場合は、を使用することでパフォーマンスがわずかに（おそらく測定できない）低下std::mapすることがわかります。
マップは、キーによって値にアクセスするためのものです。これを行わない場合、マップはコンテナにとって悪い選択です。
于 2012-10-02T18:38:46.460 に答える
6
を変更していない場合vector<pair<string,string> >（何度も繰り返すだけ）、を使用するとパフォーマンスが低下しmapます。これは、typicalmapがオブジェクトのバイナリツリーで構成されており、各オブジェクトを異なるメモリブロックに割り当てることができるためです（独自のアロケータを作成しない限り）。さらに、の各ノードはmap隣接オブジェクトへのポインタを管理するため、時間とメモリのオーバーヘッドも発生します。ただし、キーによる検索はO（log）操作です。一方、vectorデータを1つのブロックに保持するため、通常、プロセッサキャッシュの方が快適です。ベクトルでの検索は、実際にはO（N）演算であり、それほど良くはありませんが、許容範囲内です。ソートされたベクトルでの検索は、lower_boundなどの関数を使用してO（log）にアップグレードできます。
これは、このデータに対して実行する操作によって異なります。多くの検索を行う場合はunordered_map、このコンテナのキーによる検索はO（1）操作であるため、ハッシュコンテナを使用する方がおそらく良いでしょう。前述のように、反復するvector方が高速です。
stringおそらくあなたの中で交換する価値がありますpairが、これはあなたがそこに何を持っているか、そしてどのようにコンテナにアクセスするかに大きく依存します。
于 2012-10-02T18:47:54.453 に答える
5
答えは、これらのデータ構造で何をしているか、およびそれらのサイズによって異なります。に数千の要素があり、要素を何度std::vector<std::pair<std::stringm std::string> >も検索し続ける場合firstは、を使用するstd::map<std::string, std::string>とパフォーマンスが向上する可能性があります（std::unordered_map<std::string, std::string>代わりに、このユースケースでの使用を検討することをお勧めします）。ベクトルが比較的小さく、要素を中央にあまり頻繁に挿入しようとしない場合は、ベクトルを使用する方がはるかに高速な場合があります。要素を反復処理するだけの場合、ベクトルはマップよりもはるかに高速です。反復処理は実際にはその強みの1つではありません。要素の数がそれほど少なくないと仮定すると、マップは物事を調べるのに適しています。そうしないと、ベクトルの線形検索がさらに高速になるためです。
時間が費やされている場所を特定する最良の方法は、コードのプロファイルを作成することです。多くの場合、時間が費やされている場所を事前に完全に明確にすることはできません。多くの場合、疑わしいホットスポットは実際には問題がなく、他の領域では予期しないパフォーマンスの問題が発生します。たとえば、あいまいな場所で参照するのではなく、オブジェクトに私の値を渡す場合があります。
于 2012-10-02T18:45:54.627 に答える
1
ルックアップを実行する前に多くの挿入を実行するような使用パターンの場合、要素がオンデマンドでソートされる「レイジー」マップを実装することでメリットが得られる場合があります（つまり、イテレーターを取得するとき、ルックアップを実行するときなど）。
于 2012-10-02T18:49:54.677 に答える
0
C ++はstd::vector線形メモリ内のアイテムを並べ替えると言うので、最初に初期容量のメモリブロックを割り当て、次に新しいアイテムをベクターに挿入するときに、空きがあるかどうかを確認し、ない場合は新しいアイテムを割り当てます。より多くのスペースでバッファリングし、すべてのアイテムを新しいバッファにコピーして構築し、ソースバッファを削除して新しいバッファに設定します。
アイテムの挿入を開始したばかりvectorで、再割り当てが多すぎるためにアイテムがたくさんある場合は、コピーの作成とデストラクタの呼び出しを行います。
この問題を解決するために、入力項目（正確ではないが通常の長さ）を数えるとreserve、ベクトル用のメモリを確保して、再割り当てなどすべてを回避できます。std::listサイズがわからない場合は、魔女のようなコレクションを使用できますが、内部アイテムを再割り当てすることはありません。
于 2012-10-02T18:57:35.647 に答える