转置2D阵列

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上嵌入了不支持汇编的工具链)

Answer 1

在O(1)中工作的一个非常简单的解决方案是为矩阵保存一个额外的布尔值,说明它是否是"转置"的.然后将根据此布尔值(行/列或列/行)访问该数组.

当然,它会阻碍您的缓存利用率.

因此,如果您有许多转置操作,并且几乎没有"完整遍历"(顺便说一下,也可能根据布尔值重新排序),这是您的最佳选择.

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

然后,您将shuffle指令应用于前两个向量(交错其奇数元素,A0B0 C0D0 - > ABCD,并交叉它们的偶数元素,0A0B 0C0D - > ABCD),并将其应用于最后两个,以创建一组新的向量每个2x2块转置:

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

最后,您将shuffle指令应用于奇数对和偶数对(组合它们的第一对元素,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个元素向量执行此类操作.