多次元配列のこれらの2つの実装の間にこのような実行時間の差があるのはなぜですか？

Question

私は最近、次のようにあるコメントに出会っ：

多次元配列は、配列アクセスのために多くの時間がかかります。キャッシュとアクセス速度を向上させるには、インデックスを小から大に、つまりrmq[1002][1002][11][11]ではなくrmq[11][11][1002][1002]のような配列をrmqと宣言することをお勧めします。

私は同じことをテストするコードを試しました。コード1：

int pre_compute[18][100001]; //global variable 

int main(){ 
    /*some precomputations on pre_compute array 
    of the order of size of the array*/ 

    /*Run 10^8 queries on pre_compute array, 
    O(1) per query.*/ 
} 

コード2：

int pre_compute[100001][18]; //global variable 

int main(){ 
    /*exact same precomputations on pre_compute array as done in Code 1 
    of the order of size of the array*/ 

    /*Run 10^8 queries on pre_compute array, 
    O(1) per query.*/ 
} 

両方のコード配列の分布を除いて同一です。それでも、2つのコード間に大きな実行時間差がありました。最初のコードは私のPCで平均で0.40 secsでしたが、他のコードは平均で1.42 secsでした。

配列の2つの実装の間にこのような大きな実行時間差が生じる理由は何でしょうか？

Answer 1

これは、行 - 主順序行列と列 - 主順序行列との違いです。アレイの列の連続した要素をメモリに連続して、行優先順に

;

差がWikipediaに説明されています列の主要な順序では、列の連続する要素は連続しています。

CおよびC++は行メジャーなので、局所的な理由で行のキャッシュを活用できます。これは、スピードアップの劇的な増加を説明します。

技術的には、時間を大幅に節約したい場合は、多次元配列を1D配列として表現する方がよい場合があります。 :)