c - 遍历二维数组的二维子数组的最佳方法是什么？

Question

如果我有一个二维数组，使用 for 循环遍历整个数组、一行或一列是微不足道的。然而，偶尔，我需要遍历任意二维子数组。

一个很好的例子是数独游戏，我可以在其中将整个网格存储在二维数组中，但随后需要分析 9 个正方形的每个单独 block 。目前，我会做类似下面的事情:

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 是“行优先”排序的，这意味着访问 block 将导致每次迭代都出现缓存未命中!那是因为内存不是连续访问的。

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