4

非常に大きな可能性のある数のベクトルを繰り返し処理し、偶数要素と奇数要素を新しい別のベクトルにコピーする必要があるとしましょう。(ソース ベクトルは、奇数に対する偶数の比率を持つことができます。すべてが偶数、すべてが奇数、またはその中間である可能性があります。)

簡単にするために、push_backは次のような場合によく使用されます。

for (std::size_t Index; Index < Source.size(); Index++)
{
    if (Source[Index] % 2) Odds.push_back(Source[Index]);
    else Evens.push_back(Source[Index]);
}

ただし、パフォーマンスが最優先される並べ替えアルゴリズムなどの実装の一部として使用すると、これが非効率的で有害になるのではないかと心配しています。たとえば、QuickSort では、このように要素を分離します。

事前にメモリを割り当てるために使用できるreserve()ため、必要な割り当ては 1 つだけですが、ソース ベクター全体を 2 回反復する必要があります。

もちろん、ソース ベクトルのサイズと同じ量のスペースを割り当てることもできます。これは、新しいベクトルがそれ以上保持する必要がないためです。

私が見逃しているより良い方法はありますか？push_back()プログラマーにとってこの種のことを管理することは通常信頼されていますか、それとも機密性の高いアルゴリズムにとって負担になる可能性がありますか?

4

5 に答える 5

9

push_back()「重いアルゴリズムの内部ループでは避けるべきですか?」という質問に答えるつもりです。他の人があなたの投稿を読んだように見えるのではなく、「大きなベクトルで無関係な並べ替えを行う前に push_back を呼び出しても問題ありませんか?」また、引用や査読記事を追い求めるのに時間を費やすのではなく、私の経験から回答します。

あなたの例は、基本的に、合計 CPU コストになる 2 つのことを行っています。入力ベクトルの要素を読み取って操作し、要素を出力ベクトルに挿入する必要があります。次の理由により、要素を挿入するコストが心配です。

  1. push_back() は、ベクトルに追加要素用に十分なスペースが事前に予約されている場合は一定時間 (実際には瞬間的) ですが、予約スペースが不足すると遅くなります。
  2. メモリの割り当てにはコストがかかります（衒学者が何か違うふりをしていても、malloc()ただ遅いです）new
  3. 再割り当て後にベクターのデータをある領域から別の領域にコピーするのも遅くなります: push_back() が十分なスペースがないことを発見すると、より大きなベクターを割り当ててから、すべての要素をコピーする必要があります。(理論的には、サイズが多くの OS ページであるベクトルの場合、STL の魔法の実装は、VMM を使用して、コピーせずに仮想アドレス空間内でそれらを移動することができます。
  4. 出力ベクトルを過剰に割り当てると問題が発生します。フラグメンテーションが発生し、将来の割り当てが遅くなります。データキャッシュを燃やし、すべてを遅くします。永続的な場合、不足している空きメモリが占​​有され、PC でのディスク ページングや組み込みプラットフォームでのクラッシュが発生します。
  5. ベクトルの再割り当ては O(n) 操作であり、 m回の再割り当ては O(m×n) であるため、出力ベクトルの割り当て不足は問題を引き起こします。STL のデフォルト アロケータが指数再割り当てを使用する場合 (再割り当てするたびにベクトルの予約を以前のサイズの 2 倍にする)、線形アルゴリズムは O(n + n log m) になります。

したがって、あなたの本能は正しいです。push_back が遅いためではなく、遅い再割り当てを引き起こす可能性があるため、可能な場合は常にベクトル用にスペースを事前予約してください。また、 の実装をshrink_to_fit見ると、コピーの再割り当ても行われ、メモリ コストが一時的に 2 倍になり、さらに断片化が発生することがわかります。

ここでの問題は、出力ベクトルに必要なスペースが常に正確にわかっているとは限らないことです。通常の対応は、ヒューリスティックと、場合によってはカスタム アロケータを使用することです。デフォルトで、出力ベクトルごとに入力サイズの n/2+k を予約します。ここで、k は安全マージンです。そうすれば、入力が適度にバランスが取れている限り、通常は出力に十分なスペースがあり、push_back は、そうでないまれなケースで再割り当てできます。push_back の指数関数的な動作がメモリを浪費しすぎていることがわかった場合 (実際には n+2 が必要なときに 2n 要素を予約する原因となります)、ベクトル サイズをより小さく拡張するカスタム アロケータを与えることができます。

事前に入力要素を調べずに、正確な量のスペースを常に予約する方法はありません。ただし、バランスが通常どのように見えるかを知っている場合は、ヒューリスティックを使用して適切な推測を行い、多くの反復で統計的なパフォーマンスを向上させることができます。

于 2011-07-25T01:41:59.283 に答える
2

もちろん、ソース ベクトルのサイズと同じ量のスペースを割り当てることもできます。これは、新しいベクトルがそれ以上保持する必要がないためです。

次に、への呼び出しでそれをフォローアップしますshrink_to_fit

ただし、これは非効率的であり、並べ替えアルゴリズムなどに害を及ぼすのではないかと心配しています。... push_back() は通常、プログラマーにとってこの種のことを管理するために信頼されていますか、それとも機密性の高いアルゴリズムにとって負担になる可能性がありますか?

はい、push_back は信頼されています。正直なところ、あなたの懸念の意味がわかりません。おそらく、ベクトルでアルゴリズムを使用している場合は、要素を既にベクトルに入れています。ベクトル要素がどのようにそこに到達したかが重要な場合、どのようなアルゴリズムについて話しているのpush_backですか?

于 2011-07-24T02:28:35.400 に答える
2

すべての偶数をすべての確率の前に置くカスタム述語で元のベクトルをソートするのはどうですか?

bool EvenBeforeOdd(int a, int b)
{
  if ((a - b)  % 2 == 0) return a < b;

  return a % 2 == 0;
}

std::sort(v.begin(), v.end(), EvenBeforeOdd);

次に、最大の偶数を見つける必要があります。これは、たとえばupper_bound、非常に大きな偶数などで行うことができます。それを見つけたら、範囲の非常に安価なコピーを作成できます。

更新: @Blastfurnace がコメントしたように、各パーティション内で順序付けされた要素を実際には必要としないため、std::partitionよりも使用する方がはるかに効率的です。sort

bool isEven(int a) { return 0 == a % 2; }
std::vector<int>::const_iterator it =  std::partition(v.begin(), v.end(), isEven);

std::vector<int> evens, odds;
evens.reserve(std::distance(v.begin(), it);
odds.reserve(std::distance(it, v.end());

std::copy(v.begin(), it, std::back_inserter(evens));
std::copy(it, v.end(), std::back_inserter(odds));
于 2011-07-24T02:33:01.473 に答える
1

オブジェクトが動的に作成される場合、ベクトルは文字通りポインターを格納するだけです。これにより、特に内部再割り当てに関しては、ベクトルが大幅に効率化されます。同じオブジェクトが複数の場所に存在する場合、これによりメモリも節約されます。

std::vector<YourObject*> Evens;

注: 関数のコンテキストからポインターをプッシュしないでください。これにより、そのフレームの外側でデータが破損する可能性があります。代わりに、オブジェクトを動的に割り当てる必要があります。

これはあなたの問題を解決しないかもしれませんが、おそらく役に立ちます。

于 2011-07-24T02:28:46.517 に答える
1

サブベクトルがちょうど半分 (奇数/偶数) の場合は、それぞれに元のベクトルの 50% を割り当てるだけです。これにより、無駄を省くことができshrink_to_fitます。

于 2011-07-24T02:30:21.137 に答える