c++ - 高效的子阵列 (2D) 访问

Question

注意:我愿意接受更好标题的建议..

想象一个 n x n square，存储为整数数组。

生成 n 的最有效方法是什么？ - 每个 n 中整数的长度数组非重叠 sqrt(n) x sqrt(n)子方 block ？

一个特例 ( n=9 ) 是数独，如果我们想要小方 block 中的数字。

我能想到的唯一方法是:

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

但这看起来很疯狂，如果你能原谅我这个双关语的话。

有没有人有更有效的建议？

Answer 1

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

只有一种可能的次优性:缓存行的不完整使用。如果 s 不是缓存行的倍数，您的子方 block 将在缓存行的中间结束，导致部分数据从内存中获取两次。然而，这只是一个问题，如果你的子方 block 不再适合缓存，所以你需要一个非常大的问题大小来触发它。 对于数独方 block ，没有比您提供的方法更快的方法了。

要解决这个缓存行问题(一旦您确定这确实值得!)，您可以一次一行地遍历矩阵，为 ciel(n/sqrt(n))< 聚合数据 输出数组中的子方 block 。这将按以下方式交换循环:

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++){

但是，只有当您在遍历单个子方 block 时需要保留的中间数据很小时，这才会奏效。如果您像您一样需要将整个数据复制到一个临时数组中，您将一无所获。

---

如果你真的想优化，尽量不要将数据存储在临时 subseq 数组中。尝试直接解释从矩阵中读取的数据。如果您确实要检查数独方 block ，则可以避免使用此临时数组。

---

从你提出问题的方式来看，我推测你的目标是将每个子方 block 中的数据依次传递给分析函数。如果是这种情况，您只需将指向 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]);
        }
    }
}

现在您可以通过改变前两个参数将任何二维子数组形状传递给您的分析函数，并完全避免复制。