高效子数组（二维数组）访问

Question

NB: 我很乐意听取有关更好标题的建议……

想象一个存储为整数数组的 nxn 正方形。

如何最有效地生成一个长度为 n 的整数数组，其中包含每个 sqrt(n)xsqrt(n) 子方块中的整数，并且这些子方块不重叠？

这是数独游戏的一个特例（n=9），如果我们想要在较小的方格中放置数字。

我能想到的唯一方法类似于：

int square[n][n], subsq[n], len;

int s = sqrt(n);

for(int j=0; j<n; j+=s){
    for(int i=0; i<n; i+=s){
        //square[i][j] is the top-left of each sub-square
        len = 0;
        for(int y=j; y<j+s; y++){
            for(int x=i; x<i+s; x++){
                subsq[len] = square[x][y];
                len++;
            }
        }
    }
}

但这似乎有些疯狂，如果您原谅我的双关语。

有没有更有效的建议？

- OJFord

---

@NiklasB。这是什么？我想这确实是我问题的很大一部分。由于四重循环，它对我来说似乎很恶劣。我想知道是否有更好的解决方案，因为该数组存储在连续的内存中。 - OJFord

@OllieFord：嗯，你目前没有按顺序访问数组。你正在内存中跳来跳去。通过使第二个索引比第一个索引变化更快，可以提高缓存行性能。除此之外，循环是算法性的，与2D数组关系不大。 - Ed S.

@Ollie 如果你仔细想一下，这个循环的总复杂度是O(n^2)。但我认为问题在于你的问题不够清晰。你想要实现什么？你只是想要一个公式来计算元素subsq[i]的二维坐标吗？ - Niklas B.

修改问题以开头说明n是一个完全平方数。 - Camille Goudeseune

@OllieFord 只需计算内部循环迭代的次数。每个单元格都需要一次。你有n^2个单元格。 - Niklas B.

Answer 1

尽管存在四级循环，但您最多只访问每个数组元素一次，因此您的方法的复杂度为O(n^2)，而不是四层循环所表明的O(n^4)。并且，由于您实际上想要查看所有元素，因此这接近最优解。

唯一可能存在的次优性在于：未完全使用缓存行。如果s不是缓存行的倍数，则您的子正方形将以缓存行的中间结束，导致从内存中获取数据的部分被重复获取。然而，只有在您的子正方形不再适合缓存时才会出现这个问题，因此您需要一个非常大的问题规模来触发它。对于数独方格而言，您给出的方法已经是最快的了。

要解决这个缓存行问题（一旦确定这确实值得），您可以逐行遍历矩阵，在输出数组中聚合ciel(n/sqrt(n))个子正方形的数据。这将以以下方式交换循环：

for(int j=0; j<n; j+=s){
    for(int y=j; y<j+s; y++){
        for(int i=0; i<n; i+=s){
            for(int x=i; x<i+s; x++){

然而，只有当在遍历单个子方格时需要保存的中间数据很少时，此方法才有效。如果需要像复制整个数据到临时数组中那样复制整个数据，你将无法获得任何优势。

---

如果你真的想要优化，请尝试摆脱存储在临时subseq数组中的数据。尝试直接从矩阵中读取数据并直接解释它。如果你确实在检查数独方格，则可以避免使用这个临时数组。

---

从你提出问题的方式来看，我推测你的目标是依次将每个子方块的数据传递给分析函数。如果是这样，你可以像这样将指向2D子数组的指针传递给函数：

void analyse(int width, int height, int (*subsquare)[n]) {
    for(int y = 0; y < height; y++) {
        for(int x = 0; x < width; x++) {
            subsquare[y][x];    //do anything you like with this value
        }
    }
}

int main() {
    int square[n][n], subsq[n], len;
    int s = sqrt(n);

    for(int j=0; j<n; j+=s){
        for(int i=0; i<n; i+=s){
            analyse(s, s, (int (*)[n])&square[i][j]);
        }
    }
}

现在，您只需要通过更改前两个参数来传递任何2D子数组形状到分析函数中，完全避免复制。

- cmaster - reinstate monica