2

そのため、さまざまな状況でのさまざまな STL コンテナーのパフォーマンス比較について、さまざまな質問、ブログ投稿、記事などを読むのに何時間も費やしてきました。

ただし、正確な状況(3D ゲーム)の適切なソースをまだ見つけることができませんでした。

私はいくつかのクラスへのポインタを多数（間違いなく5k以上、おそらく50k未満）収集しています（正確な性質は関係ないと思います）、任意の位置までの距離を決定する単一のfloat値でそれらをソートしたいこれはフレーム中に変化しません)。

その後、格納された各ポインターを反復処理したいと思います。ここでは順序が重要なので、並べ替えを行います。

擬似コードの状況は次のとおりです。

// A: Insertion
foreach (class instance that needs sorting):
    container.insert( pair(distanceOfInstance, instance) );

// B: Sorting - using the distanceOfInstance as the determining factor
container.sort();

// C: Iteration in sorted order
foreach (pair in container)
    doSomethingWith(pair.instance);

このプロセス全体がゲームの各フレームで (潜在的に) 繰り返されるため、ここでの最適なパフォーマンスは重要です。コンテナーは、毎回A の前にクリアする必要があります。Cの後、他に何も行われません。

私が必要としないもの (繰り返しますが、必要ありません):

  • コンテナへのランダムアクセス。
  • コンテナがソートされた後に新しい要素を挿入する機能。

現在、私が最も速いと考えたのは、ベクターまたはセットのいずれかを使用することです。しかし、私の状況では、要素をベクターに挿入して並べ替え、各要素を 1 回反復する方が速いかどうかはわかりません。または、要素をセットに挿入して (挿入中に並べ替えて)、各要素を 1 回反復する方が高速な場合。

私たちのプロジェクトでは、他のいくつかのタスクにもブーストを使用しているため、ブースト内のより良い解決策 (またはまったく別のもの) を誰かが知っている場合は、提案をお待ちしています。また、この質問がすでに回答されていて、見つけられなかった場合は申し訳ありません:)

4

5 に答える 5

1

パフォーマンスは常に注意が必要です。両方の方法で実装し、どちらがより良い出力をもたらすかを測定する必要があります。

そうは言っても、作成時に十分な要素を予約する場合は、ベクターの方が適していると思います。セットを使用すると、新しく挿入された要素は挿入のたびにセットにソートされます。ベクトルを使用すると、そのコストが一度に発生します。

于 2013-10-25T08:47:35.147 に答える
1

他の回答で述べたように、状況ではベクトルを使用する必要があります。時間の複雑さに関しては、ベクトルのソートには時間がかかりますO(n log n)ここで、nは挿入する要素の数です。の場合std::set、既にソートされたシーケンスは、1 回の挿入ごとにO(log n)のコストがかかります。n 個の要素を挿入すると、実行時間もO(n log n)になります。ただし、ベクトル ソリューションは、メモリの局所性が優れているため高速になります (つまり、1 つの連続したメモリ範囲に格納され、高速に読み書きできます)。

さらに、std::vector一定のスペース オーバーヘッドしかありませんstd::setが、リニア オーバーヘッドがあります (通常はRb-treeとして実装されます)。

反復回数が多く、nが大きい場合は、反復ごとにベクトルのメモリを割り当てないようにしてください。だから代わりに

while (true) {
  vector<YourClass*> container;
  container.reserve(numInstancesInCurrentIteration);
  // your code, insertions with 'container.emplace_back(...)'
}

これと同様のことを行います：

vector<pair<float, YourClass*> > container;
while (true) {
  if (container.size() < numInstancesInCurrentIteration)
    container.resize(numInstances, pair<float, YourClass*>(-1.f, NULL));

  // A: Insert using assignments
  size_t pos = 0;
  foreach (class instance that needs sorting):  // pseudo-code
    container[pos++] = make_pair(distanceOfInstance, &instance);

  // B: Sort only the used range
  std::sort(container.begin(), container.begin() + pos);

  // C: Iterate over pointers sorted by distance
  for (auto it = container.begin(); it != container.begin() + pos; ++it)
    doSomethingWith(it->second);
}

いくつかの反復の後、への呼び出しはcontainer.resize()非常にまれになります。の呼び出しは、doSomethingWith(YourClass*)おそらくプログラムの中で最もコストのかかる部分になります。

于 2013-10-28T18:45:59.033 に答える
1

要素を一度だけソートする必要がある場合は、ベクターを使用するとパフォーマンスが向上すると思います。リストの使用を検討することもできますが、ベクトルよりも少し遅くなると思います。

于 2013-10-25T08:44:58.090 に答える
0

他のみんなが答えたように、私もベクターを使います。これはよりシンプルで、オブジェクトのメモリ レイアウトにより多くアクセスできます。

于 2013-10-28T19:09:32.007 に答える