0

符号なしの整数 ID フィールドを持つ約 70 ～ 150 の異なる構造体 X があります。これらは、プログラムの初期化時に読み込まれて初期化され、その後変更されることはありません。それらにアクセスするための最速の方法 (頻繁に発生します) は、次の (または他の方法?) の中でどれですか?

  1. std::vector v; を使用します。ここで、v[X.id] = X; X& x = v[id]; を実行してアクセスします。(これは最初にコピーを行う必要がありますが、後で基本的にフラットな配列で id によるルックアップを行うだけです。

  2. 上記と同じですが、std::vector v; X* x = v[id]; これにはもう 1 つのレベルの間接性があるため、私はこれについて警戒しています。

  3. a std::map - 上記に比べてやり過ぎのように感じますか?

  4. 上記と同じですが、unordered_map - 繰り返しますが、70 ～ 150 回のオカレンスが提案 3 に勝るものはありません。

  5. もっと賢いものはありますか？1 で見られる問題の 1 つは、アクセス パターンが少しまばらである可能性があることですが、それが最速の方法である場合に対処する方法がわからないことです。

4

3 に答える 3

5

ベクトルを使用するのが間違いなく最速のアプローチです。

  • ベクトルの複雑さはO（1）です。検索やハッシュを行う必要はありません。すぐにインスタンスが見つかります。
  • マップの複雑さはO（log N）です。マップは、インスタンスを見つけるために、インデックスをlogNの他のエントリと比較する必要があります。
  • Unordered_mapの複雑さはO（1）ですが、ハッシュ値の計算にかなりのオーバーヘッドがあります（ただし、単純な数値の場合はそれほど多くはありません）。ただし、std :: unordered_mapは、1つのハッシュインデックスの背後に複数のエントリを配置するため、1つのインデックスを比較する代わりに、複数のインデックスを比較する必要があります（デフォルトでは4だと思います）。
于 2012-06-06T17:05:02.710 に答える
2

少数のアイテムの場合、一定時間のアクセスを提供するため、配列またはベクトルのデータ型を使用するよりも高速にアクセスする方法はないと思います。多くのオブジェクトの場合、このアプローチも最速ですが、メモリが最も高価です。

于 2012-06-06T17:01:34.460 に答える
0

事前にすべての構造にスペースを事前に割り当ててもかまわず、ID を順番に並べてインデックスにもできる場合は、アプローチ 1 を使用してください。

構造体の構築にコストがかかる場合は、構築コードをデフォルトのコンストラクターに実際に配置しない (そして後でメソッド呼び出しを介して明示的に行う) か、未加工の配列を使用して、その配列内のメモリ "スロット" にnew を配置することにより、構築を遅らせます。 .

ID が連続していない場合はstd::unordered_map、「穴」のスペースの無駄を防ぐために使用します。

于 2012-06-06T17:07:51.737 に答える