11

重複の可能性：
正確に8192個の要素をループすると、プログラムが遅くなるのはなぜですか？

私は、2D配列の要素を単純に合計するために使用しているプログラムをいじくり回してきました。タイプミスは、少なくとも私には、いくつかの非常に奇妙な結果につながったようです。

配列を扱う場合、matrix [SIZE] [SIZE]：

for(int row = 0; row < SIZE; ++row)
    for(int col = 0; col < SIZE; ++col)
        sum1 += matrix[row][col];

非常に高速に実行されますが、上記の行sum1...が変更されています。

sum2 += matrix[col][row]

気づかずに偶然に行ったように、ランタイムが大幅に増加していることに気づきました。どうしてこれなの？

4

5 に答える 5

15

これは、プログラムのキャッシュ動作が原因です。

配列はメモリの連続したブロックであるため、[行] [列]にアクセスすると、メモリに順番にアクセスします。これは、アクセスしているデータページが同じページ上にあるため、アクセスがはるかに高速であることを意味します。

[column] [row]を実行すると、そのメモリに順番にアクセスしなくなるため、キャッシュミスが増え、プログラムの実行速度が大幅に低下します。

于 2012-10-26T19:28:15.537 に答える
5

matrix[row][col]とのメモリ位置matrix[row][col + 1]は隣接しています。

とのメモリ位置はmatrix[row][col]、matrix[row + 1][col]アイテムのSIZE量で区切られています。

コンピュータは、ランダムではなく順次メモリにアクセスするのが好きなので、隣接するアクセスはより高速です。アナロジーで考えると、ハードドライブのパフォーマンスは、ランダムな読み取り/書き込みよりもシーケンシャルな読み取り/書き込みの方が常に優れています。これは、CPUがメモリをキャッシュし、次に必要なものを予測しようとする方法と関係があります。

于 2012-10-26T19:31:21.480 に答える
3

これは、より高速なケースでは、線形に反復しているため、CPUのメモリプリフェッチが実際に役立つためです。遅いケースでは、メモリを飛び回っているので、データがキャッシュにある可能性が低いため、プリフェッチはほとんど効果がありません。

于 2012-10-26T19:28:30.513 に答える
3

マトリックスの順序によって異なります。行メジャーまたは列メジャーのいずれかで配列にアクセスしています。メモリへの保存方法に応じて、速度は2つの間で異なります

于 2012-10-26T19:30:05.973 に答える
-5

2次元配列は単なるポインタへのポインタです。だからそれはのように見えます

[*p][*p][*p]
  |   |   |
  v   v   v
 [d] [d] [d]
 |a| |a| |a|
 |t| |t| |t|
 [a] [a] [a]

したがって、非メイン配列（このポインターが示すもの）でデータを呼び出すと、OSはそのデータをCPUキャッシュに入れます。

于 2012-10-26T19:44:46.017 に答える