百萬級二維數(shù)組遍歷：行優(yōu)先循環(huán)還是列優(yōu)先循環(huán)更快？

百萬級二維數(shù)組高效遍歷：循環(huán)順序優(yōu)化

處理超大二維數(shù)組時(shí)，循環(huán)遍歷的順序直接影響程序效率。本文分析遍歷一個(gè)100萬元素（假設(shè)size為1000）二維數(shù)組matrix[x][y]的兩種循環(huán)方式的性能差異，并解釋其原因。

問題： 我們有兩種遍歷matrix[x][y]的方法：

方法一（行優(yōu)先）：

for (int x = 0; x < size; x++) {   for (int y = 0; y < size; y++) {     // ...操作...   } }

方法二（列優(yōu)先）：

for (int y = 0; y < size; y++) {   for (int x = 0; x < size; x++) {     // ...操作...   } }

哪種方法更快？為什么？

答案與分析：

雖然直覺上兩種方法差異不大，但實(shí)際測試表明存在顯著性能差距。這并非編譯器優(yōu)化導(dǎo)致，而是內(nèi)存訪問機(jī)制決定的。

二維數(shù)組通常以行優(yōu)先方式存儲在內(nèi)存中。matrix[x][y]的內(nèi)存地址與x和y的值密切相關(guān)。方法一（行優(yōu)先遍歷）導(dǎo)致內(nèi)存訪問跳躍式進(jìn)行。訪問matrix[x][y]時(shí)，程序先訪問matrix[x][0]，再訪問matrix[x][1]，依次類推。當(dāng)內(nèi)層循環(huán)結(jié)束，下一個(gè)訪問元素matrix[x+1][0]與matrix[x][size-1]在內(nèi)存中相距較遠(yuǎn)，造成緩存未命中，降低效率。

方法二（列優(yōu)先遍歷）則相反，內(nèi)存訪問更連續(xù)。程序依次訪問matrix[0][y], matrix[1][y], matrix[2][y]…，這些元素在內(nèi)存中連續(xù)存儲，充分利用CPU緩存，提高效率。這類似于線性掃描一維數(shù)組。

因此，對于行優(yōu)先存儲的二維數(shù)組，列優(yōu)先遍歷（方法二）通常比行優(yōu)先遍歷（方法一）更快，因?yàn)樗玫乩昧薈PU緩存機(jī)制，減少了緩存未命中的次數(shù)。