百萬級二維數組遍歷：行優先還是列優先效率更高？

百萬級二維數組遍歷效率：行優先勝列優先

處理超大二維數組時，遍歷順序對程序效率影響巨大。本文分析行優先和列優先遍歷一個約百萬元素的二維數組 matrix[x][y] 的性能差異。

問題： 我們用兩個循環嵌套分別進行行優先和列優先遍歷，對數組進行賦值：

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

雖然看起來差別細微，但實際測試結果顯示行優先遍歷速度顯著更快。

原因：內存存儲與緩存機制

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

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

結論： 處理大型二維數組時，優先選擇行優先遍歷能顯著提高程序效率。 這源于計算機內存的存儲方式和CPU緩存機制的特性。