10

私は現在、C++でベクトルを使用してアプリケーションを作成しています。

事前最適化がすべての悪の根源であることを私は知っています。

しかし、私は本当に好奇心をそそられずにはいられません。

他のベクトルの一部を別のベクトルに追加しています。
ベクトルのサイズは300を変更しないと言います。

私はいつもベクトルの最後に追加するので

実行する方が速いですか：
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

または、追加したいベクトルをループして、各アイテムを個別に（事前に予約しながら）またはで追加する方が速いでしょうpush_backかemplace。（どちらが速いかわからない）

誰でもこれについて私を助けることができますか？

4

3 に答える 3

10

一般的な原則は次のとおりです。ライブラリがとの両方do_x_onceを提供する場合do_x_in_batch、後者は少なくともdo_x_once単純なループで呼び出すのと同じくらい高速である必要があります。そうでない場合は、単純なループでより高速なバージョンを取得できるため、ライブラリの実装が非常に悪くなります。多くの場合、このようなバッチ関数/メソッドは、データ構造の内部に関する知識を持っているため、追加の最適化を実行できます。

したがって、少なくともループ内と同じくらい高速でinsertある必要があります。この特定のケースでは、のスマートな実装は、挿入するすべての要素に対して単一のことを実行できます。ベクトルの容量を毎回チェックする必要があります。ライブラリの裏をかくことを試みないでください:)push_backinsertreservepush_back

于 2013-02-21T18:31:00.410 に答える
5

コンパイラ（ライブラリの実装）、コンパイルオプション、アーキテクチャに本当に依存していると思います。Intel Xeonで最適化（/ Od）を使用せずにVS2005でクイックベンチマークを実行する：

std::vector<int> a;
std::vector<int> b;

// fill 'a' with random values for giggles

timer.start()
// copy values from 'a' to 'b'
timer.stop()

「値をコピー...」のこれらのさまざまな方法を使用して、10000000アイテムのこれらの結果を取得します。

  1. 'b'のスペースを予約してから、b.push_back(a[i]);：0.808秒を使用してforループ
  2. 'b'のサイズを変更してから、インデックス割り当てを使用してforループb[i] = a[i];：0.264秒
  3. 'b'のサイズ変更なし、ちょうどb.insert(b.end(), a.begin(), a.end());：0.021秒（最初の予約との有意差なし）
  4. std::copy(a.begin(), a.end(), std::back_inserter(b));：0.944秒（最初に予備で0.871）
  5. 'b'のサイズを変更してから、ベースポインタのメモリコピーmemcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));：0.061秒

ただし、最適化をオン（/ Ox）にすると、話は別になります。差別化を図るには、サイズを100000000に増やす必要がありました。

  1. push_backループ：0.659秒
  2. インデックスループ：0.482秒
  3. 挿入：0.210秒（最初の予備との有意差なし）
  4. std :: copy：0.422秒、最初に予約済み。それなしでbad_allocを手に入れました。
  5. memcpy：0.329秒

注目すべき興味深い点は、最適化の有無にかかわらず、挿入メソッドが線形にスケーリングされることです。他の方法は、最適化なしでは明らかに非効率的でしたが、それでもそれらを使用するとそれほど速くはなりませんでした。James Kanzeが指摘したように、g++では異なります。独自のプラットフォームでテストを実行して検証します。

于 2013-03-22T14:56:23.720 に答える
4

larsmansが言うように、1回のライブラリ呼び出しで行う回数が多いほど、効率が高くなる可能性が高くなります。ベクターへの場合insert 、ライブラリは通常、最大で1回の再割り当てを実行し、シフトされた各要素を最大で1回コピーします。ループとを使用するとpush_back、数回再割り当てされる可能性があり、大幅に遅くなる可能性があります（桁違いに）。

ただし、タイプによっては、次のようなことを行う方が速い場合もあります。

a.resize( 300 );
std::copy( b.begin(), b.end(), a.end() - 300 );

intIntelマシンでg++を使用する単純なスカラータイプ（のような）の場合、これはより高速であることがわかりました 。

于 2013-02-21T18:40:26.020 に答える