0

std::map を使用していくつかのキーと値のペアを格納することにより、数値シミュレーション用のプログラムを作成しています。マップは、シミュレーション中に展開された状態を格納するために使用されます。キーのタイプは整数であり、キーに対応する値は、同じキーに対していくつのコピーがあるかを示します。つまり、std::map です。シミュレーションの各ステップで、同じキーに対していくつの値があるかを計算する必要があるため、次のコードで確認します。

if (map[key]>0) {do something here with the number of copies}

ただし、マップにそのようなキーがなくても、マップ[キー]を呼び出すたびに、そのキーのプレースホルダーが生成され、値がゼロに設定されるため、このコードが機能しないことがすぐにわかります。したがって、私は常に std::map.size() によってキーの総数を過大評価しています。後でコードを次のように変更して、代わりにキーを検索します

if (map.find(key)!=map.end()) {...}

では、マップのキーが存在するかどうかを確認する唯一かつ最速の方法はありますか? シミュレーションを数億回実行すると、キーをチェックするために上記のコードが頻繁に呼び出されます。代わりに map.find() を使用するには遅すぎますか? ありがとう。

4

4 に答える 4

2

メンバー関数は、キーが既にマップにあるかどうかを確認するためのfindおそらく最速の方法です。とはいえ、マップ内のアイテムを順番に反復処理する必要がない場合は、std::unordered_map代わりに を使用するとパフォーマンスが向上する可能性があります。

于 2012-04-19T04:48:25.330 に答える
1

std::mapor ハッシュテーブル ( std::unordered_map) では、関数は添字演算子findを使用するのと同じくらい高速です。[]実際、要素を挿入する必要がないため、要素が見つからない場合の方が高速です。

于 2012-04-19T04:47:40.663 に答える
1

キーの存在を確認するさまざまな方法の速度に大きな違いはないと思います。一方、キーが整数で範囲がわかっている場合は、配列をそのまま使用できます。

ところで:単純な配列、ベクトル、マップ、順序付けされていないマップの速度に興味を持ちました。100000000 コンテナー [n]++ を実行する単純なプログラムを作成しました。ここで、n は 0 から 10000 の範囲の乱数です。結果は次のとおりです。

  • アレイ: 1.27 秒
  • ベクトル: 1.36s
  • 順序付けられていないマップ: 2.6 秒
  • map: 11.6s この単純なケースでのループ + インデックス計算のオーバーヘッドは ~0.8s です。

したがって、それはすべて、他の場所で費やされる時間に依存します。それがかなり多い場合 (100000000 回の反復あたり)、何を使用しても問題ありません。しかし、そうでない場合は、かなりの違いになる可能性があります。

于 2012-04-19T04:49:08.763 に答える
0

hash_map を使用できます。これは、キー値型の最速のデータ構造です。

マップも使用できますが、hash_map よりも低速です

于 2012-04-19T08:08:11.817 に答える