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

百萬級(jí)二維數(shù)組遍歷效率：行優(yōu)先勝列優(yōu)先

處理超大二維數(shù)組時(shí)，遍歷順序?qū)Τ绦蛐视绊懢薮蟆１疚姆治鲂袃?yōu)先和列優(yōu)先遍歷一個(gè)約百萬元素的二維數(shù)組 matrix[x][y] 的性能差異。

問題： 我們用兩個(gè)循環(huán)嵌套分別進(jìn)行行優(yōu)先和列優(yōu)先遍歷，對(duì)數(shù)組進(jìn)行賦值：

// 行優(yōu)先遍歷 for (int x = 0; x < size; x++) {   for (int y = 0; y < size; y++) {     matrix[x][y] = ...;    } }  // 列優(yōu)先遍歷 for (int y = 0; y < size; y++) {   for (int x = 0; x < size; x++) {     matrix[x][y] = ...;   } }

雖然看起來差別細(xì)微，但實(shí)際測(cè)試結(jié)果顯示行優(yōu)先遍歷速度顯著更快。

原因：內(nèi)存存儲(chǔ)與緩存機(jī)制

二維數(shù)組通常以行優(yōu)先方式存儲(chǔ)在內(nèi)存中。這意味著 matrix[x][y] 的內(nèi)存地址在 x 不變，y 遞增時(shí)是連續(xù)的。行優(yōu)先遍歷順序訪問這些連續(xù)地址，充分利用CPU緩存，減少內(nèi)存訪問次數(shù)，提升效率。

相反，列優(yōu)先遍歷訪問的內(nèi)存地址在內(nèi)存中是離散的，導(dǎo)致緩存命中率下降。程序頻繁地從主內(nèi)存讀取數(shù)據(jù)，造成速度變慢。 這就像從書架取書，行優(yōu)先如同從同一層取書，列優(yōu)先則需在不同層之間切換，后者耗時(shí)更多。

結(jié)論： 處理大型二維數(shù)組時(shí)，優(yōu)先選擇行優(yōu)先遍歷能顯著提高程序效率。 這源于計(jì)算機(jī)內(nèi)存的存儲(chǔ)方式和CPU緩存機(jī)制的特性。