百萬(wàn)級(jí)二維數(shù)組遍歷：行優(yōu)先還是列優(yōu)先更有效？

優(yōu)化百萬(wàn)級(jí)二維數(shù)組遍歷：行優(yōu)先還是列優(yōu)先？

本文分析了高效遍歷100萬(wàn)級(jí)二維數(shù)組 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++) {     // ...操作...   } }

雖然兩種方法看起來(lái)只是循環(huán)順序不同，但實(shí)際測(cè)試表明，行優(yōu)先遍歷（方法一）顯著快于列優(yōu)先遍歷（方法二）。

這是因?yàn)橛?jì)算機(jī)內(nèi)存通常采用行優(yōu)先存儲(chǔ)方式。方法一符合內(nèi)存布局，充分利用CPU緩存的空間局部性，減少內(nèi)存訪問(wèn)次數(shù)，提高效率。而方法二則導(dǎo)致CPU緩存命中率降低，頻繁訪問(wèn)內(nèi)存，性能下降。 可以將方法一比作連續(xù)讀取數(shù)據(jù)，方法二則像在內(nèi)存中跳躍式讀取，后者耗時(shí)更多。

盡管匯編層面的指令差異可能很小，但由于內(nèi)存訪問(wèn)模式的差異，行優(yōu)先遍歷在實(shí)際運(yùn)行中展現(xiàn)出明顯的性能優(yōu)勢(shì)。 這說(shuō)明高效代碼編寫需要充分考慮數(shù)據(jù)結(jié)構(gòu)的內(nèi)存存儲(chǔ)方式和CPU緩存機(jī)制，才能最大限度地優(yōu)化程序性能。