3

正確な数字はわかりませんが、頑張ります。最初に入力された10000要素の両端キューがあります。各要素をスキャンして、20個の要素ごとに新しい要素を挿入する必要があります。挿入は現在の位置で行われ、おそらく1要素後ろで行われます。

位置を正確に覚えておく必要はありませんが、ランダムアクセスも正確に必要ではありません。高速挿入が欲しいのですが。dequeとvectorには、挿入時に支払う高額な料金がありますか？リストを使用する必要がありますか？

私の他のオプションは、2番目の両端キューリストを作成し、各要素を調べながら、話している挿入を行う必要がない限り、それを他の両端キューリストに挿入することです。これは、パフォーマンスを重視するアプリとして高速である必要があります。しかし、私は多くのポインター（各要素はポインターです）を使用していますが、それを回避する方法がないので、L1キャッシュが常に失われると想定する必要がありますか？

4

6 に答える 6

4

std::vectorこの場合から始めますがstd::vector、質量の突然変異に2番目を使用しreserve()、次にswap()ベクトルを使用します。

アップデート

これは次の一般的な形式を取ります。

std:vector<t_object*> source; // << source already holds 10000 elements

std:vector<t_object*> tmp;

// to minimize reallocations and frees to 1 and 1, if possible.
// if you do not swap or have to grow more, reserving can really work against you.
tmp.reserve(aMeaningfulReserveValue);

while (performingMassMutation) {
  // "i scan through each element and lets every 20 elements"
  for (twentyElements)
    tmp.push_back(source[readPos++]);

  // "every 20 elements i'll need to insert an new element"
  tmp.push_back(newElement);
}

// approximately 500 iterations later…

source.swap(tmp);

Borealidは、測定という良い点を提起しました。実行は、stdライブラリの実装、データサイズ、コピーの複雑さなどによって大幅に異なります。

私の構成では、このサイズのコレクションの生のポインターの場合、vectorマスミューテーションpush_back以上はstd::list挿入よりも7倍高速でした。の範囲挿入push_backよりも速かった。vector

Emileが以下で指摘するように、std::vector::swap()要素を移動したり再割り当てしたりする必要はありません。内部を交換するだけです（アロケータが同じタイプの場合）。

于 2012-02-12T08:09:15.943 に答える
3

まず、すべてのパフォーマンスの質問に対する答えは「ベンチマーク」です。いつも。今...

メモリのオーバーヘッドを気にせず、ランダムアクセスは必要ないが、一定時間の挿入を気にする場合listは、おそらく適切です。

std::vector十分な容量がある場合、最後に一定時間挿入されます。容量を超えると、線形時間コピーが必要になります。deque個別の割り当てをリンクし、完全なコピーを回避し、フロントで一定時間の挿入を実行できるため、より優れています。ランダム挿入（20要素ごと）は常に線形時間になります。

キャッシュの局所性に関しては、avectorは（連続メモリ）を取得できる限り優れていますが、ルックアップではなく挿入を気にかけているとおっしゃいました。私の経験では、その場合、スキャンしてダンプするときにキャッシュがどれだけ熱くなるかは気にしないので、list動作の悪さはそれほど重要ではありません。

于 2012-02-12T08:03:47.947 に答える
2

リストは、コレクションの途中に要素を頻繁に挿入する場合、または要素を頻繁に削除する場合に役立ちます。ただし、リストの読み取りは遅くなります。

ベクトルは、コレクションの最後で要素を追加または削除するだけの場合は読み取りが非常に高速で、非常に高速ですが、中央に要素を挿入する場合は非常に低速です。これは、新しい要素のためのスペースを確保するために、すべての要素を目的の位置の後に1か所移動する必要があるためです。

Dequesは基本的に二重にリンクされたリストであり、ベクトルとして使用できます。

コレクションの途中に要素を挿入する必要がない場合（順序は関係ありません）、ベクターを使用することをお勧めします。ベクトルに最初から導入される要素の数を概算できる場合は、最初std::vector::reserveから必要なメモリを割り当てるためにも使用する必要があります。渡す値はreserve正確である必要はなく、概算である必要があります。必要以上に小さい場合は、必要に応じてベクトルのサイズが自動的に変更されます。

于 2012-02-12T08:08:02.123 に答える
2

2つの方法があります。リストは常にランダムな場所の挿入のオプションですが、すべての要素を個別に割り当てると、パフォーマンスにも影響があります。dequeにインプレースで挿入する他のオプションも、適切ではありません。挿入ごとに線形の時間を支払うためです。ここでは、新しい両端キューに挿入するというアイデアが最適かもしれません-2倍のメモリを支払いますが、一方で、常に2番目の両端キューの最後、またはその前の1つの要素のいずれかで挿入を行います-これはすべて一定の償却時間を与えます、それでもコンテナのキャッシュは良好です。

于 2012-02-12T08:10:19.097 に答える
2

etcに対して行われるコピーの数はstd::vector/deque ::insert、挿入位置とコンテナの終わりの間の要素の数（スペースを空けるためにシフトする必要がある要素の数）に比例します。aの最悪のケースstd::vectorはO(N)、コンテナの前面に挿入した場合です。したがって、要素を挿入する場合M、最悪の場合はそれO(M*N)は良くありません。

コンテナの容量を超えた場合にも、再割り当てが発生する可能性があります。十分なスペースを前もって確保することで、再割り当てを防ぐことができ::reserveます。

他の提案もあります。2番目のコンテナーにコピーする方が、複雑std::vector/dequeさを実現するために常に編成できるという点で優れている可能性がありますが、2つのコンテナーを一時的に保管する必要があります。O(N)

astd::listを使用すると、インプレース挿入を実現できますがO(1)、追加のメモリオーバーヘッド（リストポインタの格納など）とメモリの局所性の低下（リストノードが連続して割り当てられない）が犠牲になります。プールされたメモリアロケータを使用することで、メモリの局所性を向上させることができます（プールをブーストする可能性がありますか？）。

全体として、どちらが「最速」のアプローチであるかを実際に分類するには、ベンチマークを行う必要があります。

お役に立てれば。

于 2012-02-12T08:13:20.250 に答える
1

vector途中で高速挿入が必要であるが、ランダムアクセスを気にせず、deque間違いなくあなたに適していない場合：それらの場合、何かを挿入するたびに、その要素と最後の間のすべての要素を移動する必要があります。ビルトインコンテナの中で、listほぼ間違いなくあなたの最善の策です。ただし、シナリオに適したデータ構造は、キャッシュの局所性が優れているため、おそらくVListですが、C++標準ライブラリでは提供されていません。ウィキペディアのページはC++実装にリンクしていますが、インターフェイスのクイックビューからは、完全にSTL互換ではないようです。これがあなたにとっての問題かどうかはわかりません。

もちろん、最終的にどちらが最適なソリューションであるかを確認する唯一の方法は、パフォーマンスを測定することです。

于 2012-02-12T08:11:59.823 に答える