5

マップのようなデータ構造が必要ですが、各キーにはそれに関連する複数の値が含まれる場合がありますが、単一のキーに対応するすべての値をオブジェクトの配列として取得する必要があります。したがって、これを行うにはどのデータ構造が最適でしょうか。データ構造を検索する必要はありません。特定のキーに対応するすべての値にすばやくアクセスする必要があるだけです。std::multimap を調べましたが、特定のキーのすべての値が返されるわけではありません。では、私が使用できる C++ の最適なデータ構造はどれでしょうか?

4

2 に答える 2

6

地図のようなデータ構造が必要ですが...

std::map<key, std::vector<value>>

8,000 万ポイントは素晴らしい値です。他のオプションを検討する価値があります。少し検討/実験/ベンチマークする価値のあるものは次のとおりです。

  • スパース ダイレクト インデックス作成...これを実現するには、8,000 万のデータ ポイントだけでなく、それらがまたがる x/y/z 空間全体に十分なメモリが必要ですが、[x][y][z]ルックアップを実行してセル ID のベクトルを見つけることができます -それは明らかに巨大になるでしょう-それが実行可能か望ましいかは、問題の説明からは明らかではありません

  • ソートされたベクトル...データ構造要素の挿入とルックアップの順序/重複、および圧縮ステップstd::mapを実行できるかどうかによって異なります- (x、y、z)値をソートすると、の連続したメモリ使用量std::vectorstd::vectorbinary_searchstd::mapvector

  • std::unordered_map<key, std::vector<value>>...たとえば1億バケット容量のサイズ変更により、挿入が少し高速化されるはずです。これは、他のオプションよりも遅くなったり速くなったりする可能性があります...スパースインデックス作成よりもインデックスのメモリページが少ない可能性がありますが、binary_search連続したメモリよりも多く、ルックアップごとにアクセスされるメモリページが最小ですが、通常のハッシュ技術を使用すると、 x、y、z 座標がわずかに異なる場合でも、効果的にランダムな (ただし反復可能な) ハッシュ バケットにヒットするため、上記の他のすべてのオプションよりもキャッシュ ヒットが悪化する可能性があります。

実際のベンチマークは常に最適な調整方法であり、できればコストが予想される理由によるものであることを確認するためのプロファイルを使用することをお勧めします。

于 2013-06-07T06:07:39.127 に答える
4

@TonyD による回答は確かに問題ありませんが、

std::multimap<key, value>

特定のキーのすべての値を検索すると、同じO(log N)複雑さが得られます

auto result = my_multimap.equal_range(my_key);

反復はまだO(N)複雑です。

for (auto it = result.first; it != result.second; ++it)
     // bla

ただし、すべての実際の実装では、上記の反復は、ベースの場合に得られる連続した反復でstd::multimapはなく、「連続した」値要素を追跡するノードベースのポインターを実行しています。これは、 cache-localityの理由で問題になる場合があります。std::vectorstd::map

std::vectorこのソリューションからわかる主な欠点は、データをコピーする頻度によっては、すべての値をまとめて保持することを約束しているため、オーバーヘッドが発生する可能性があることです。

このmultimapアプローチにより、コンテナから単一の値を挿入/抽出することも容易になります

my_multimap.insert(std::make_pair(some_key, another_value);

対

auto it = my_map.find(some_key);
if (it != my_map.end()) 
    it->second.push_back(another_value);
else
    my_map.insert(std::make_pair(some_key, another_value));

プログラムをベンチマークして、どのコンテナーがより便利かを確認する必要があります。

于 2013-06-07T09:01:37.850 に答える