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

Question

如果我有一个2D数组,通过使用for循环遍历整个数组,行或列是微不足道的.但是,偶尔我需要遍历任意2D子阵列.

一个很好的例子是数独,其中我可以将整个网格存储在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是"row-major"有序,这意味着访问block将导致每次迭代失效!那是因为没有连续访问内存.

有一个类似的问题grid.您的嵌套循环秩序是解决i不同之前j,但你正在访问grid的j作为行.这又不是连续的,并且会在每次迭代时缓存未命中.

因此,处理嵌套循环和多维数组时的经验法则是将循环索引和数组索引放在相同的顺序中.对于你的代码,那就是

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
    }
}