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

百萬級二維數(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ù)。

? 版權(quán)聲明
THE END
喜歡就支持一下吧
點(diǎn)贊9 分享