1. CPU高速緩存：在電腦系統中，CPU高速緩存（英語：CPU Cache）是用於減少處理器訪問記憶體所需平均時間的部件。在金字塔式存儲體系中它位於自頂向下的第二層，僅次於CPU寄存器。其容量遠小於記憶體，但速度卻可以接近處理器的頻率。當處理器發出記憶體訪問請求時，會先查看緩存內是否有請求數據。如果存 ...
1. CPU高速緩存：在電腦系統中，CPU高速緩存（英語：CPU Cache）是用於減少處理器訪問記憶體所需平均時間的部件。在金字塔式存儲體系中它位於自頂向下的第二層，僅次於CPU寄存器。其容量遠小於記憶體，但速度卻可以接近處理器的頻率。當處理器發出記憶體訪問請求時，會先查看緩存內是否有請求數據。如果存在（命中），則不經訪問記憶體直接返回該數據；如果不存在（失效），則要先把記憶體中的相應數據載入緩存，再將其返回處理器。緩存之所以有效，主要是因為程式運行時對記憶體的訪問呈現局部性（Locality）特征。這種局部性既包括空間局部性（Spatial Locality），也包括時間局部性（Temporal Locality）。有效利用這種局部性，緩存可以達到極高的命中率。（百度百科解釋）。
2.二維數組有兩種遍歷方式，一種是先行後列，一種是先列後行，代碼實現也很簡單，用兩個for迴圈嵌套即可，錶面上看來，二者時間複雜度都是O(mn),但實際上，效率的是通過記憶體頁面交換次數和Cache命中率的高低來判斷的。
3.先行後列的效率要高的多，這個與二維數組的存儲方式有關(記憶體中，上一行的尾部地址和下一行的頭部地址連續)。
情況一：如果申請的空間在記憶體之中，也就是說讀取只需要看cache是否命中，未命中再到記憶體中讀取。而cache從記憶體中抓取一般都是整個數據塊，所以它的物理記憶體是連續的，對於較大的數組而言，幾乎讀取的數據都是同行不同列的（因為cache很小，所以對於較大的數組一般只會拿一行內的數據），而如果內迴圈以列的方式進行遍歷的話，將會使整個緩存塊無法被利用，而不得不從記憶體中讀取數據，而從記憶體讀取速度是遠遠小於從緩存中讀取數據的。隨著數組元素越來越多，按列讀取速度也會越來越慢。
情況二：申請的為虛擬記憶體（當然程式認為還是連續的物理記憶體，是操作系統在磁碟另開闢的空間），虛擬記憶體到物理記憶體需要經過地址映射，如果虛擬記憶體採用頁式地址映射（不討論快表技術，僅分析頁表在記憶體中），最好的情況是每次映射的頁內數據都可以被使用，這樣可以減少頁面調度的次數,從而提升效率。
例如：對於int a[128][1024];假設記憶體頁大小為4096位元組(一個int 占4個位元組)，該數組每行正好占據一個記憶體頁的空間，若按先行後列遍歷，外層迴圈每走一行，內層走過1024個元素正好一頁，沒發生頁面調度，遍歷完整個數組頁面調度次數最多為128次；若按先列後行，則每遍歷一個元素，都發生一次頁面調度，因為列上每個元素位於同行內（不同頁），遍歷整個數組頁面調度次數可能達到1024*128次；實際中由於物理記憶體足夠（記憶體頁較大，分配給進程的頁框數多等因素），調度次數會減少很多。
4.總結：對於二維數組的遍歷效率優化，其實就是更好的利用程式申請記憶體而產生的空間局部性，這種局部性在很多地方都有體現，二維數組只是簡單的一個例子，一個好的程式可以合理減少缺頁發生的次數，提高程式的空間局部性，從而提高運行效率。
簡易代碼（實際結果很可能因為申請記憶體位置不同或記憶體大小而產生偏差）：
#include <stdio.h>
#include <stdlib.h>
#define M 10000
#define N 20000
int main(){
int MyArray[M][N];
int i,j;
//先行後列方式遍歷
for( i = 0;i < M;i++){
for(j = 0;j < N;j++){
MyArray[i][j] = 0;
}
}
}
#include <stdio.h>
#include <stdlib.h>
#define M 10000
#define N 20000
int main(){
int MyArray[M][N];
int i,j;
//先列後行方式遍歷
for( i = 0;i < N;i++){
for(j = 0;j < M;j++){
MyArray[j][i] = 0;
}
}
}
參考文章
[1] 小白xiaoxiao.二維數組兩種遍歷的比較
http://blog.sina.com.cn/s/blog_707d31f50101j2e7.html
[2] 哆啦A熊.二維數組按行和按列遍歷的效率
https://blog.csdn.net/shuffle_ts/article/details/89420651
