你如何有效地转置矩阵? 是否有这样的库,或者你会使用什么算法?
例如:
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上嵌入了不支持汇编的工具链)
在某些情况下,有这样的库。 而且,值得注意的是,您可以使用矢量化数据(例如,128位向量中的四个32位元素,但这也适用于32位寄存器中的四个8位字节),以便比单个数据更快 – 元素访问。
对于转置,标准的想法是使用“shuffle”指令,它允许您以任何顺序从两个现有向量中创建新的数据向量。 您使用输入数组的4×4块。 所以,从开始,你有:
v0 = 1 2 3 4 v1 = 5 6 7 8 v2 = 9 ABC v3 = DEF 0
然后,将shuffle指令应用于前两个向量(交错其奇数元素,A0B0 C0D0 – > ABCD,并交织它们的偶数元素,0A0B 0C0D – > ABCD),并将其应用于最后两个向量,以创建一组新的向量每个2×2块转置:
1 5 3 7 2 6 4 8 9 DBF AEC 0
最后,您将shuffle指令应用于奇数对和偶数对(组合它们的第一对元素,AB00 CD00 – > ABCD,以及它们的最后一对,00AB 00CD – > ABCD),以获得:
1 5 9 D 2 6 AE 3 7 BF 4 8 C 0
在那里,16个元素转换为8个指令!
现在,对于32位寄存器中的8位字节,ARM没有准确的随机指令,但是您可以使用移位和SEL(选择)指令来合成所需的内容,并且可以在一个指令中进行第二组混洗。使用PKHBT(打包半字底部顶部)和PKHTB(打包半字顶部底部)指令进行指导。
最后,如果您正在使用具有NEON矢量化的大型ARM处理器,则可以使用16×16块上的16个元素向量执行此类操作。
在O(1)中工作的一个非常简单的解决方案是为矩阵保存一个额外的布尔值,说明它是否“转置”。 然后将根据此布尔值(行/列或列/行)访问数组。
当然,它会阻碍您的缓存利用率。
因此,如果您有许多转置操作,并且几乎没有“完整遍历”(顺便说一下,也可能根据布尔值重新排序),这是您的最佳选择。
维基百科有一篇关于就地矩阵转置的文章。 对于非平方矩阵,这是一个非平凡的,相当有趣的问题(使用小于O(N x M)的内存,即)。 这篇文章链接到很多有算法的论文,以及一些源代码。
请注意 – 正如我在对您的问题的评论中所说,您的演示不是标准换位,所有算法都将针对此进行编写。
(标准转置函数将为您的示例数据提供此结果:)
{ {1, 4}, {2, 5}, {3, 6} };
如果您只是这样做以在屏幕上显示图像,那么在将图像复制到后台缓冲区时,最好只进行换位,而不是在原位移位然后进行blitting。
基本上,您在行上迭代并使用匹配的列项交换每个项目。 您可以通过交换行索引和列索引来获取匹配项。 当您处理完所有列后,转置就完成了。 您也可以反过来并迭代列。
如果要提高性能,可以将整行复制到临时数组中,将完整匹配列复制到另一行,然后将其复制回来。 如果你使用memcopy进行涉及最内层元素的传输,它应该稍微快一点(即使这个策略涉及另外一个变量赋值)。
如果内存不是瓶颈,我建议使用临时矩阵。 这真的很容易,无论如何它可能会更快。
但在某些情况下,我理解这是不可能的,通常是在准备数据供某些现有硬件或库访问时。
这里最有效的解决方案是在将数据从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,在这种情况下它肯定能够进行旋转,当将图像blit到屏幕时让GPU进行旋转会更有效率。
只是一个简单的复制到临时和复制,转移,使用指针步进避免乘法地址计算,内循环展开:
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++; } }
由于问题的性质,我不知道如何避免缓存局部性问题。
需要了解更多c/c++开发分享转置2Darrays,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享转置2Darrays相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979668.html