12

ネストされた for ループ構造があり、現在、各反復の開始時にベクトルを再宣言しています。

void function (n1,n2,bound,etc){

    for (int i=0; i<bound; i++){
             vector< vector<long long> > vec(n1, vector<long long>(n2));
             //about three more for-loops here
    }
}

これにより、反復ごとに「新しく始める」ことができます。これは、内部操作が主に vec[a][b] += 何らかの値の形式であるため、うまく機能します。ただ、n1やn2が大きいと遅いのではないかと心配です。ベクトル/配列/などの基礎となるアーキテクチャがわからないため、この状況を処理するための最速の方法がわかりません。代わりに配列を使用する必要がありますか? 別の方法でクリアする必要がありますか？ロジックをまったく別の方法で処理する必要がありますか?

編集: ベクトルのサイズは、技術的には反復ごとに変更されません (ただし、関数のパラメーターに基づいて変更される場合があります)。私は単にそれをクリアしようとしているだけなので、プログラムは他のすべての状況を考慮して人間的に可能な限り高速です。

編集：

さまざまな方法の私の結果:

Timings (for a sample set of data):
reclaring vector method: 111623 ms
clearing/resizing method: 126451 ms
looping/setting to 0 method: 88686 ms
4

8 に答える 8

12

私は小さなスコープを明確に好みます (つまり、変数がそこでのみ使用される場合は、最も内側のループで変数を宣言します) が、大きなサイズの場合、これにより多くの割り当てが発生する可能性があります。

したがって、このループがパフォーマンスの問題である場合は、ループの外側で変数を宣言し、ループの内側で単純にクリアしてみてください。ただし、これはベクトルの (予約された) サイズが同じままである場合にのみ有利です。ベクトルのサイズを変更している場合は、とにかく再割り当てが発生します。

生の配列を使用しないでください。何の利点も得られず、問題が発生するだけです。

于 2012-04-13T13:23:50.270 に答える
10

いくつかの異なるメソッドをテストするコードを次に示します。

#include <chrono>
#include <iostream>
#include <vector>

int main()
{
  typedef std::chrono::high_resolution_clock clock;

  unsigned n1 = 1000;
  unsigned n2 = 1000;

  // Original method
  {
    auto start = clock::now();
    for (unsigned i = 0; i < 10000; ++i)
    {
      std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
      // vec is initialized to zero already

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }


  // reinitialize values to zero at every pass in the loop
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      // initialize vec to zero at the start of every loop
      for (unsigned j = 0; j < n1; ++j)
        for (unsigned k = 0; k < n2; ++k)
            vec[j][k] = 0;

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }

  // clearing the vector this way is not optimal since it will destruct the
  // inner vectors
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      vec.clear();
      vec.resize(n1, std::vector<long long>(n2));

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }

  // equivalent to the second method from above
  // no performace penalty
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      for (unsigned j = 0; j < n1; ++j)
      {
        vec[j].clear();
        vec[j].resize(n2);
      }

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }
}

編集: メソッドをより公平に比較​​するためにコードを更新しました。 編集 2 : コードを少しクリーンアップしました。方法 2 または 4 が適しています。

私のコンピューターでの上記の4つの方法のタイミングは次のとおりです。

16327389
15216024
16371469
15279471

ポイントは、さまざまな方法を試して、コードをプロファイリングする必要があるということです。

于 2012-04-13T13:48:57.527 に答える
6

コンテナーを選択するとき、私は通常、この図を使用して助けてくれます。

ここに画像の説明を入力

ソース

それ以外、

これがパフォーマンスの問題を引き起こしている場合は、以前に投稿したように、 for ループの外側でコンテナーを宣言し、各反復の開始時にそれをクリアするだけです

于 2012-04-13T13:29:25.790 に答える
0

反復ごとにベクトル値を 0 にリセットする必要があるため、実際には、この質問は「ループ内の計算と比較して、ベクトルのメモリの割り当てと割り当て解除のコストが安いか高いか」に要約されます。

計算がアルゴリズムの高価な部分であると仮定すると、それをコーディングした方法は明確で簡潔であり、意図した範囲を示しており、おそらく代替アプローチと同じくらい高速です。

ただし、計算と更新が非常に高速で、ベクトルの割り当て/割り当て解除が比較的高価な場合は、ループを介した各反復の最後/最初に配列にゼロを埋めるために使用できますstd::fill。

もちろん、確実に知る唯一の方法は、プロファイラーで測定することです。あなたが取ったアプローチは、どのような種類のホットスポットとしても表示されず、明らかなコードをそのままにしておく必要があることに気付くと思います.

于 2012-04-13T14:40:32.247 に答える
0

パフォーマンスを本当に気にしている (そして and のサイズを事前に知っているn1)n2が、C スタイルの配列を使用したくないstd::array場合は、あなたの友人かもしれません。

編集:あなたの編集を考えるとstd::array、ベクターサイズは各反復で変更されませんが、コンパイル前にはまだ不明であるため、適切な代替ではないようです。

于 2012-04-13T13:31:00.987 に答える
0

そのようなものではないのはなぜですか：

{
    vector< vector<long long> > vec(n1, vector<long long>(n2));

    for (int i=0; i<bound; i++){

         //about three more for-loops here

         vec.clear();
    }
}

編集：スコープブレースを追加しました;-)

于 2012-04-13T13:28:42.657 に答える
0

以前のコメントに加えて:

Robinson の swap メソッドを使用すると、その swap を非同期に処理することでさらに高速化できます。

于 2012-04-13T13:28:57.147 に答える
-1

特にベクトルから多くの有用な機能を取得している場合は、ベクトルと配列を使用するオーバーヘッドはわずかです。内部的に、ベクトルは配列を割り当てます。そのため、ベクターが最適です。

于 2012-04-13T13:25:35.560 に答える