"rotate"（循环移位）二维数组有什么好方法？

Question

这确实是一个概念性（与语言无关）的问题，但为了便于解释，我将使用 C++。我更喜欢可以移植到其他语言的答案（没有指针算法或记忆技巧）。

假设我们有：

arr，我们的矩形某种任意类型的二维数组 T
void shift(int dx, int dy)，执行"rotation"
numRows,行数
numCols，列数

shift() 移动数组，使所有行都向下移动 dx 个位置，超出范围的行将回绕到开头。（同样对于列和 dy。）假设这是我们的数组最初的样子：

{{a1, a2, a3, a4},
 {b1, b2, b3, b4},
 {c1, c2, c3, c4},
 {d1, d2, d3, d4}};

调用我们的函数后：shift(2,1)，arr 应该如下所示：

{{c4, c1, c2, c3},
 {d4, d1, d2, d3},
 {a4, a1, a2, a3},
 {b4, b1, b2, b3}};

在这种情况下，dx 是 2，所以所有内容都向下移动了两个位置，dy是 1，所以所有内容也都移到了右边一个地方。

这是我解决这个问题的方法：

void shift(int dx, int dy)
{
   T newArr[numRows][numCols];
   for(int r = 0; r < numRows; r++)
   {
      for(int c = 0; c < numCols; c++)
         newArr[(r + dx) % numRows][(c + dy) % numCols] = arr[r][c];
   }
   for(int r = 0; r < numRows; r++)
   {
      for(int c = 0; c < numCols; c++)
         arr[r][c] = newArr[r][c];
   }
}

我对这段代码不满意，因为它既不省时也不 space 高效。我正在寻找一种更优雅的解决方案，它可以用更少的循环做更多的事情并且使用更少的内存。

Answer 1

我建议以下解决方案：

#include <stdio.h>
#include <memory>

int main() {
    const int nrows = 4, ncols = 5;
    const int dx = 2, dy = 1;
    int a[nrows ][ncols] = { {1, 2, 3, 4, 5}, 
        { 6, 7, 8, 9, 10 },
        { 11, 12, 13, 14, 15 },
        { 16, 17, 18, 19, 20 }
    };
    int tmp[nrows][ncols];
    for (int i = 0; i < nrows; i++)
        for (int j = 0; j < ncols; j++)
            tmp[(i + dx) % nrows][(j + dy) % ncols] = a[i][j];
    memcpy(a, tmp, sizeof(tmp));
    for (int i = 0; i < nrows; i++)
        for (int j = 0; j < ncols; j++)
            printf(j < ncols - 1 ? "%3d " : "%3d\n", a[i][j]);
}

Demo.

使用内存复制的替代方法特定于 c++。这是可能的，因为在连续的 c++ 内存中存储多维数组的方法。一行的最后一个元素之后是下一行的第一个元素。

#include <stdio.h>
#include <memory>

int main() {
    const int nrows = 4, ncols = 5;
    const int dx = 2, dy = 1;
    int a[nrows][ncols] = { {1, 2, 3, 4, 5},
        { 6, 7, 8, 9, 10 },
        { 11, 12, 13, 14, 15 },
        { 16, 17, 18, 19, 20 }
    };
    int tmp[nrows][ncols];
    memcpy(tmp + dx, a, (nrows - dx) * ncols * sizeof(int));
    memcpy(tmp, a + (nrows - dx), dx * ncols * sizeof(int));
    memcpy(a, tmp, sizeof(tmp));
    for (int i = 0; i < nrows; i++) {
        memcpy(tmp[i] + dy, a[i], (ncols - dy) * sizeof(int));
        memcpy(tmp[i], a[i] + ncols - dy, dy * sizeof(int));
    }

    memcpy(a, tmp, sizeof(tmp));
    for (int i = 0; i < nrows; i++)
        for (int j = 0; j < ncols; j++)
            printf(j < ncols - 1 ? "%3d " : "%3d\n", a[i][j]);
}

Demo.

Answer 2

另一种可能性是根本不移动元素。这个想法是有一个函数来转换使用的索引，使得原始数组出现旋转。

将原始数组包装成适当的数据类型会略微降低性能。但是每当你旋转（或镜像，或反转，或其他）时，你都会获得内存和时间。

Answer 3

假设您有一个较低级别的函数可以有效地复制 Matrix 的子锁（处理低级别内存排列、行优先列优先排序等...），该操作在概念上可以分解为 4 个子块副本.使用 matlab 数组符号和基于 1 的数组索引，类似于：

tmp(1:nr , 1:nc) = a(end-nr+1:end , end-nc+1:end );
tmp(1:nr , nc+1:end) = a(end-nr+1:end , 1:end-nc );
tmp(nr+1:end , 1:nc) = a(1:end-nr , end-nc+1:end );
tmp(nr+1:end , nc+1:end) = a(1:end-nr , 1:end-nc );

请注意，让低级函数完成低级工作的假设非常普遍（例如 BLAS 和 LAPACK）。

Answer 4

void scroll_left(int Array[8][8])
{
  for (u=0; u<8; u++)
  {
    for(int r=0; r<8; r++)
    {
      for (int c=0; c<8; c++)
      temp[r][c]=A[r][(c+u)%8];
    }
    delay_1(1000);
  }
}

Answer 5

这可以通过几种方式使用 O(1) 辅助 space 来完成。所有这些都是对旋转一维数组的算法的改编。为了使 descriptions/notation 简单，我假设 dx 和 dy 是正数，并假设您可以弄清楚如果它们是负数该怎么做。

针对小 dx、dy 的简单、缓慢的解决方案

有一个非常简单的算法可以在线性时间内将一维数组旋转1步：将最后一个元素存储在临时变量中，其余元素向右移动一位，然后写入临时变量变量到数组中的第一个位置。

这可以直接适用于将二维数组水平或垂直旋转 1 步，并且需要一些额外的工作，对角线。因此，您可以应用 dx 水平旋转和 dy 垂直旋转；或者你可以做 min(dx, dy) 对角线旋转，然后 max(dx, dy) - min(dx, dy) 正交旋转。

这需要 O(numRows * numCols * (dx + dy)) 时间，因此不适合大班次。但是，如果您只移动一个space，那还不够；这是最优的。

循环分解

设 a 为 GCD of numRows and dx, and b be the GCD of numRows and dy. Then the desired rotation will permute the array in a * b independent cycles of length numCols * numRows / (a * b). The GCDs can be computed in logarithmic time by Euclid's algorithm。

对于i = 0 to a - 1和j = 0 to b - 1，使用临时变量方法将循环从arr[j][i]开始旋转一步。此循环由元素 arr[j][i]、arr[j + dy][i + dx]、arr[j + 2*dy][i + 2*dx] 等组成，其中索引分别以 numRows 和 numCols 为模计算。

时间复杂度为O(numRows * numCols)，因为每个数组元素只读一次，只写一次。但是，该算法的性能可能会降低，原因有两个：它执行大量模运算（当数组维度不是 2 的幂时很糟糕），并且连续的 reads/writes 不在相邻的数组位置（当数组维度不是 2 的幂时很糟糕）整个数组不适合缓存）。

反转子数组

长度为 n 的一维数组可以通过以下算法向右旋转 k 步：

反转整个数组，
反转子数组0 .. k-1,
反转子数组k .. n-1.

我们可以通过将行旋转 dx，然后将列旋转 dy 来执行二维旋转。

该算法对每个数组元素进行四次读写，所以其时间复杂度也是O(numRows * numCols)，但比使用循环分解的算法对数组的遍历次数更多。但是，它不进行模运算，并且缓存未命中的情况可能更少。实现起来也更简单。

"rotate"（循环移位）二维数组有什么好方法？

What is a good way to "rotate" (circular shift) a two dimensional array?

language-agnostic

arrays

swap

multidimensional-array

针对小 dx、dy 的简单、缓慢的解决方案

循环分解

反转子数组