循环遍历 2D 数组的 2D 子数组的最佳方法是什么？

Question

如果我有一个 2D 数组，则使用 for 循环遍历整个数组、行或列是很简单的。然而，有时，我需要遍历任意的二维子数组。

一个很好的例子是数独，我可以将整个网格存储在 2D 数组中，但随后需要分析 9 个正方形的每个单独块。目前，我会做类似以下的事情：

for(i = 0; i < 9; i += 3) {
    for(j = 0; j < 9; j += 3) {
        for(k = 0; k < 3; k++) {
            for(m = 0; m < 3; m++) {
                block[m][k] == grid[j + m][i + k];
            }
        }

        //At this point in each iteration of i/j we will have a 2D array in block 
        //which we can then iterate over using more for loops.
    }
}

是否有更好的方法来迭代任意子数组，特别是当它们以如上所述的常规模式出现时？

Answer 1

这种循环结构的性能将是可怕的。考虑最里面的循环：

        for(m = 0; m < 3; m++) {
            block[m][k] == grid[j + m][i + k];
        }

C 是“行优先”排序的，这意味着访问块将导致每次迭代时缓存未命中！这是因为内存不是连续访问的。

grid 也存在类似的问题。您的嵌套循环顺序是在改变 j 之前修复 i，但您正在访问 j 上的 grid 作为行。这又不是连续的，并且会在每次迭代时缓存未命中。

因此，处理嵌套循环和多维数组时的经验法则是以相同的顺序放置循环索引和数组索引。对于你的代码来说，那就是

for(j = 0; j < 9; j += 3) {
    for(m = 0; m < 3; m++) {
        for(i = 0; i < 9; i += 3) {
            for(k = 0; k < 3; k++) {
                block[m][k] == grid[j + m][i + k];
            }
        }
        // make sure you access everything so that order doesn't change
        // your program's semantics
    }
}

Answer 2

就数独而言，您不能只存储 9 个 3x3 数组吗？那么您就不需要为子数组烦恼...如果您开始移动到比数独更大的网格，您也可以通过这种方式提高缓存性能。

忽略这一点，您上面的代码可以正常工作。

Answer 3

假设您有一个二维数组 a[n][m]。为了循环右上角位于位置 x,y 的子数组 qx r 使用：

for(int i = x; i < n && i < x + q; ++i)
   for(int j = y; j < m && j < y + r; ++j)
   {
      ///
   }

对于您的数独示例，您可以这样做

for(int i = 0; i<3; ++i)
    for(int j = 0; j < 3; ++j)
       for(int locali = 0; locali < 3; ++locali)
           for(int localj = 0; localkj <3; ++localj)
               //the locali,localj element of the bigger i,j 3X3 square is 
               a[3*i + locali][3*j+localj]