百万级二维数组遍历：行优先还是列优先效率更高？

百万级二维数组遍历效率：行优先胜列优先

处理超大二维数组时，遍历顺序对程序效率影响巨大。本文分析行优先和列优先遍历一个约百万元素的二维数组 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缓存机制的特性。