-4

次の演習問題を解く:

ia の要素を出力する 3 つの異なるバージョンのプログラムを作成します。1 つのバージョンでは反復を管理するために範囲を使用する必要があり、他の 2 つのバージョンでは通常の for ループを使用する必要があります。3 つのプログラムすべてで、すべての型を直接記述します。つまり、コードを単純化するために型エイリアス、auto、または decltype を使用しないでください。[C++ 入門]

疑問が生じました:配列にアクセスするためのこれらの方法のうち、速度の点で最適化されているのはどれですか?またその理由は?

私の解決策:

  1. Foreach ループ:

    int ia[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};    
for (int (&i)[4]:ia)        //1st method using for each loop
    for(int j:i)
        cout<<j<<" ";

  2. ネストされた for ループ:

    for (int i=0;i<3;i++)       //2nd method normal for loop
    for(int j=0;j<4;j++)
        cout<<ia[i][j]<<" ";

  3. ポインターの使用:

    int (*i)[4]=ia;
for(int t=0;t<3;i++,t++){  //3rd method.  using pointers.
    for(int x=0;x<4;x++)
        cout<<(*i)[x]<<" ";

  4. 使用auto:

    for(auto &i:ia)             //4th one using auto but I think it is similar to 1st.  
    for(auto j:i)
         cout<<j<<" ";

を使用したベンチマーク結果clock()

1st: 3.6  (6,4,4,3,2,3) 
2nd: 3.3  (6,3,4,2,3,2)
3rd: 3.1  (4,2,4,2,3,4)
4th: 3.6  (4,2,4,5,3,4)

各メソッドを 1000 回シミュレートします。

1st: 2.29375  2nd: 2.17592  3rd: 2.14383  4th: 2.33333
Process returned 0 (0x0)   execution time : 13.568 s

使用コンパイラ:MingW 3.2 c++11 フラグが有効。IDE:コードブロック

4

2 に答える 2

17

私はいくつかの観察と指摘があります、そしてあなたがこれからあなたの答えを得ることを願っています。

  1. あなたがあなた自身に言うように、4番目のバージョンは基本的に最初のバージョンと同じです。autoコーディングのショートカットとしてのみ考えることができます（もちろん、これは厳密には当てはまりません。使用autoすると、予想とは異なる型が取得され、実行時の動作が異なる可能性があります。ただし、ほとんどの場合、これは当てはまります）。

  2. ポインターを使用するソリューションは、ポインターを使用していると人々が言うときの意味ではない可能性があります。1つの解決策は次のようなものかもしれません：

    for (int i = 0, *p = &(ia[0][0]); i < 3 * 4; ++i, ++p)
    cout << *p << " ";

    または、2つのネストされたループを使用するには（おそらく無意味です）：

    for (int i = 0, *p = &(ia[0][0]); i < 3; ++i)
    for (int j = 0; j < 4; ++j, ++p)
        cout << *p << " ";

    これからは、これがあなたが書いたポインタソリューションだと思います。

  3. このような些細なケースでは、実行時間を絶対的に支配する部分はcoutです。簿記とループのチェックに費やされる時間は、I/Oを実行する場合と比較して完全に無視できます。したがって、どのループ手法を使用するかは重要ではありません。

  4. 最新のコンパイラは、このようなユビキタスなタスクとアクセスパターンを最適化するのに優れています（配列を反復処理します）。したがって、これらのメソッドはすべて、まったく同じコードを生成する可能性があります（ポインタバージョンは例外です。これについては後で説明します）。 ）。

  5. このようなほとんどのコードのパフォーマンスは、コンパイラがアセンブリ分岐命令（および残りの操作）を正確に生成する方法ではなく、メモリアクセスパターンに依存します。これは、必要なメモリブロックがCPUキャッシュにない場合に発生するためです。これらのバイトをRAMからフェッチするには、およそ数百CPUサイクル（これは単なるボールパーク数です）に相当する時間がかかります。すべての例はまったく同じ順序でメモリにアクセスするため、メモリとキャッシュに関する動作は同じであり、実行時間もほぼ同じになります。

    ちなみに、これらの例がメモリにアクセスする方法は、メモリにアクセスするための最良の方法です。線形、連続、最初から最後まで。繰り返しになりますが、そこには問題がcoutあり、非常に複雑な操作であり、呼び出しのたびにOSを呼び出すことさえあります。これにより、特に、CPUキャッシュから有用なものがほぼ完全に削除（削除）される可能性があります。

  6. 32ビットシステムおよびプログラムでは、anintとポインタのサイズは通常同じです（両方とも32ビットです！）。つまり、配列にインデックス値またはポインタを渡して使用するかどうかはそれほど重要ではありません。ただし、64ビットシステムでは、ポインターは64ビットですが、intは通常32ビットのままです。これは、通常、64ビットシステムおよびプログラムでは、ポインター（またはイテレーター）ではなく、配列へのインデックスを使用する方がよいことを示しています。

    ただし、この特定の例では、これはまったく重要ではありません。

  7. コードは非常に具体的で単純ですが、一般的なケースでは、ほとんどの場合、コードについてできるだけ多くの情報をコンパイラーに提供することをお勧めします。これは、仕事をするためにあなたが利用できる最も狭く、最も具体的なデバイスを使わなければならないことを意味します。これは、一般的なforループ（つまりfor (int i = 0; i < n; ++i)）がコンパイラの範囲ベースのループ（つまり）よりも悪いことを意味します。後者の場合、コンパイラは、範囲全体を反復処理し、範囲外に出ないことを単に知っているからです。一般的なループの場合、特にコードがより複雑な場合、コンパイラはこれを確認できず、コードがC++標準として実行されることを確認するために追加のチェックとテストを挿入する必要があります。すべきだと言います。forfor (auto i : v)for

  8. 多くの（ほとんどの？）ケースでは、パフォーマンスが重要だと思うかもしれませんが、そうではありません。そして、ほとんどの場合、パフォーマンスを得るために何かを書き直すと、あまり得られません。そして、ほとんどの場合、得られるパフォーマンスの向上は、維持する可読性と保守性を失う価値はありません。したがって、コードとデータ構造を正しく設計します（そしてパフォーマンスを念頭に置いてください）が、この種の「マイクロ最適化」はほとんどの場合価値がなく、コードの品質にも悪影響を与えるため、避けてください。

  9. 一般に、速度の観点からのパフォーマンスを推論するのは非常に困難です。理想的には、健全な科学的測定と統計的手法を使用して、実際の作業条件で実際のハードウェア上の実際のデータを使用して時間を測定する必要があります。コードの実行にかかる時間を測定することでさえ、決して些細なことではありません。パフォーマンスの測定は難しく、それについての推論も難しくなりますが、最近では、ボトルネックを認識してコードを最適化する唯一の方法です。

私はあなたの質問に答えたと思います。

編集：私はあなたがやろうとしていることのための非常に単純なベンチマークを書きました。コードはここにあります。これはWindows用に作成されており、Visual Studio 2012でコンパイルできる必要があります（範囲ベースのforループのため）。タイミングの結果は次のとおりです。

Simple iteration (nested loops): min:0.002140, avg:0.002160, max:0.002739
    Simple iteration (one loop): min:0.002140, avg:0.002160, max:0.002625
   Pointer iteration (one loop): min:0.002140, avg:0.002160, max:0.003149
 Range-based for (nested loops): min:0.002140, avg:0.002159, max:0.002862
 Range(const ref)(nested loops): min:0.002140, avg:0.002155, max:0.002906

関連する数値は「最小」時間です（1000x1000アレイの場合、各テストの2000回以上の実行）。ご覧のとおり、テスト間にはまったく違いはありません。コンパイラの最適化をオンにする必要があることに注意してください。そうしないと、テスト2は災害になり、ケース4と5は1と3よりも少し悪くなります。

そして、ここにテストのコードがあります：

// 1. Simple iteration (nested loops)
unsigned sum = 0;
for (unsigned i = 0; i < gc_Rows; ++i)
    for (unsigned j = 0; j < gc_Cols; ++j)
        sum += g_Data[i][j];

// 2. Simple iteration (one loop)
unsigned sum = 0;
for (unsigned i = 0; i < gc_Rows * gc_Cols; ++i)
    sum += g_Data[i / gc_Cols][i % gc_Cols];

// 3. Pointer iteration (one loop)
unsigned sum = 0;
unsigned * p = &(g_Data[0][0]);
for (unsigned i = 0; i < gc_Rows * gc_Cols; ++i)
    sum += *p++;

// 4. Range-based for (nested loops)
unsigned sum = 0;
for (auto & i : g_Data)
    for (auto j : i)
        sum += j;

// 5. Range(const ref)(nested loops)
unsigned sum = 0;
for (auto const & i : g_Data)
    for (auto const & j : i)
        sum += j;
于 2013-02-19T03:11:07.700 に答える
0

それに影響を与える多くの要因があります：

  1. コンパイラによって異なります
  2. 使用するコンパイラフラグによって異なります
  3. 使用するコンピューターによって異なります

正確な答えを知る唯一の方法は、巨大な配列（おそらく乱数ジェネレーターから）を処理するときに使用される時間を測定することです。これは、配列サイズが少なくとも1000x1000である必要があることを除いて、すでに行った方法と同じです。

于 2013-02-25T12:17:45.803 に答える