转置一个二维数组

Question

你如何高效地转置一个矩阵？是否有相关的库可供使用，或者你会使用哪种算法？

例如：

short src[W*H] = {
  {1,2,3},
  {4,5,6}
};
short dest[W*H];


rotate_90_clockwise(dest,src,W,H); //<-- magic in here, no need for in-place

//dest is now:

{
  {4, 1},
  {5, 2},
  {6, 3}
};

在我的特定情况下，src数组是原始图像数据，目标是帧缓冲区，并且我嵌入在ARM上，使用不支持汇编的工具链。

- Will

---

那可能是作业吗？;-) - mjv

这实际上不是一般的矩阵转置 - 转置将 (行,列) 映射到 (列,行)。 - caf

知道你要嵌入什么会有一点帮助。例如，拥有GPU访问权限的人可以轻松地使用点积运算。 - Pod

Answer 1

一种非常简单的O(1)解决方案是为矩阵保存一个额外的布尔值，表示矩阵是否为“转置”的状态。然后根据这个布尔值来访问数组（行/列或列/行）。

当然，这会影响你的缓存利用率。

所以如果你有很多转置操作，但是只有少量的“完整遍历”（顺便说一句，这些也可以根据布尔值进行重新排序），那么这是你最好的选择。

- Anna

---

我要点赞这个超棒的创新解决方案。只要通过API访问矩阵而不是直接访问，你就可以很容易地创建一个带有转置标志和实际数据的结构，并使用转置标志返回宽度和高度，以及在获取器和设置器中交换它们。 - paxdiablo

或者，如果您想避免人们谈论的所有缓存问题，只需同时在内存中保留正常和转置副本（setter API 可以确保它们永远不会失步）。对于这种特定情况可能不太适用（因为它是嵌入式的），但对于常规系统可能值得一试。 - paxdiablo

这是超越常规思维，但它并不是将横向的图像旋转以在竖向记忆屏幕上显示。 - Will

这要看您想对矩阵做什么。在您的情况下，您需要将其传递到屏幕上（我对图像/放置东西在屏幕上不是很熟悉），因此该方法在这里可能不是万能药。在其他情况下，您需要做的是相乘矩阵，或者在转置矩阵时访问它（从中读取）。或者找一个子矩阵等。对于上述示例，您确实需要转置矩阵（在概念上）。使用上述方法可以完全避免“实际转置”它。 - Anna

我们在重复自己。许多以某种方式呈现给用户的东西，在幕后可以完全不同，因此我不接受你关于“实际执行”的说法，尽管在图片的情况下可能是必要的。你关于它很慢的说法是错误的。你只是改变了一个布尔值，这非常快：）。稍后，当您需要访问矩阵时，许多事情可以按您希望的顺序完成。例如，如果您需要复制矩阵的子部分或更改单元格，则仅为初始转置节省了大量时间。 - Anna

Answer 2

有一些库可以完成这个任务。值得注意的是，对于向量化数据（例如，在128位向量中的四个32位元素，但也适用于32位寄存器中的四个8位字节），您可以使用一些技巧来提高速度，而不是进行单个元素访问。

对于转置操作，标准的想法是使用“shuffle”指令，允许您以任何顺序从两个现有的向量创建新的数据向量。您需要使用输入数组的4x4块。因此，初始状态如下：

v0 = 1 2 3 4
v1 = 5 6 7 8
v2 = 9 A B C
v3 = D E F 0

接着，您将洗牌指令应用于前两个向量（交错它们的奇数元素，A0B0 C0D0 -> ABCD，以及交错它们的偶数元素，0A0B 0C0D -> ABCD），并对最后两个向量执行相同操作，从而创建一个新的向量集合，其中每个2x2块都被转置：

1 5 3 7
2 6 4 8
9 D B F
A E C 0

最后，您对奇偶对应用洗牌指令（将它们的第一对元素AB00 CD00组合为ABCD，将它们的最后一对元素00AB 00CD组合为ABCD），以得到：

1 5 9 D
2 6 A E
3 7 B F
4 8 C 0

在那里，16个元素通过8条指令进行了转置！

现在，对于32位寄存器中的8位字节，ARM没有精确的洗牌指令，但您可以使用移位和SEL（选择）指令合成所需内容，并且第二组洗牌可以在一条指令中使用PKHBT（打包半字底部顶部）和PKHTB（打包半字顶部底部）指令执行。

最后，如果您正在使用具有NEON向量化的大型ARM处理器，则可以在16x16块上的16元素向量中执行类似于此的操作。

- Brooks Moses

---

这是一个正确的矩阵转置（第一行变为第一列），问题中给出的示例是矩阵旋转（第一行变为第二列）。 - Skizz

Answer 3

维基百科上有一篇关于原地矩阵转置的完整文章。对于非方阵，这是一个相当有趣但不平凡的问题（同时使用少于O(N x M)的内存）。该文章链接了很多算法论文以及一些源代码。

需要注意的是，如我在您的问题评论中所说，您的演示并非标准转置，所有算法都将针对标准转置编写。

（标准转置函数将为您的示例数据提供此结果:)）

{
  {1, 4},
  {2, 5},
  {3, 6}
};

如果您只是想在屏幕上显示图像，最好在将图像复制到后备缓冲区时进行转置，而不是就地转置然后再进行位块传送。

- caf

Answer 4

• 如果矩阵是方形的或者您不需要原地转置，那么很容易实现：

基本上，您可以在行上迭代并与匹配的列项交换每个项。通过交换行和列索引，您可以获得匹配项。当您处理完所有列时，转置就完成了。您也可以反过来迭代列。

如果您想提高性能，可以将一个完整的行复制到临时数组中，将完整的匹配列复制到另一个数组中，然后将它们复制回去。如果使用内部元素涉及传输，则应该稍微快一些（即使此策略涉及更多变量分配）。

• 如果矩阵不是方形的（如您的示例），那么在原地进行转置就会非常棘手。由于转置不会改变内存需求，因此仍然可能在原地进行转置，但是如果您粗心大意，就会覆盖另一行或列的元素。

如果内存不是瓶颈，我建议使用临时矩阵。这样做真的很容易，而且可能会更快。

• 最好的方法是根本不进行转置，而只是在某个地方设置一个标志，指示您是按行还是按列访问数据。在大多数情况下，需要转置的算法可以重写为访问未经转置的矩阵。要实现这一点，您只需要重写一些基本操作，例如接受具有一种方向或另一种方向的矩阵的矩阵乘积。

但在某些情况下，我理解这是不可能的，通常是因为正在准备数据以供某些现有硬件或库访问。

- kriss

Answer 5

这里最有效的解决方案是在从RAM复制到帧缓冲区时旋转数据。将源在RAM中旋转，然后将结果复制到帧缓冲区的速度最多只有复制和旋转版本的一半。因此，问题是，按顺序读取并随机写入还是随机读取并按顺序写入更有效率。在代码中，这将是以下两种选择之间的选择：

// read sequential
src = { image data }
dest = framebuffer
for (y = 0 ; y < H ; ++y)
{
   for (x = 0 ; x < W ; ++x)
   {
     pixel = *src++
     dest [y,x] = pixel
   }
}

或者：

// write sequential
src = { image data }
dest = framebuffer
for (x = 0 ; x < W ; ++x)
{
   for (y = 0 ; y < H ; ++y)
   {
     pixel = src [x,y]
     *dest++ = pixel
   }
}

只有通过对代码进行分析才能确定答案。

现在，如果您有GPU，那么它肯定具有旋转功能，并且在将图像传输到屏幕时让GPU执行旋转操作会更加高效。

- Skizz

---

这是我的起点，但我一直在尝试在多个扫描线上拥有“光标”，假设会减少缓存未命中。 - Will

Answer 6

只需简单地将数据复制到临时变量中，同时进行转置，并使用指针步进来避免地址计算中的乘法，内部循环展开：

char temp[W*H];
char* ptemp = temp;
memcpy(temp, array, sizeof(char)*W*H);
for (i = 0; i < H; i++){
    char* parray = &array[i];
    for (j = 0; j+8 <= W; j += 8, ptemp += 8){
        *parray = ptemp[0]; parray += H;
        *parray = ptemp[1]; parray += H;
        *parray = ptemp[2]; parray += H;
        *parray = ptemp[3]; parray += H;
        *parray = ptemp[4]; parray += H;
        *parray = ptemp[5]; parray += H;
        *parray = ptemp[6]; parray += H;
        *parray = ptemp[7]; parray += H;
    }
    for (; j < W; j++, parray += H){
        *parray = *ptemp++;
    }
}

由于问题的本质，我不知道如何避免缓存局部性问题。

- Mike Dunlavey