我想要一个可以减少或消除这种差异的数据结构。实际上,只需要这种结构的名称,我自己就可以实现它。如果答案涉及到此类库,则也可接受,但它们应该能够与C ++一起使用。
我有一个需要快速执行图像卷积而无需硬件加速的应用程序,虽然我知道通常的优化技术可以完成这种事情,但我认为专门的数据结构或数据排序可能会提高性能。
你可以将你的二维矩阵想象成一个大螺旋,从中心开始向外扩展。展开这个螺旋,并按照这个顺序存储数据,地址之间的距离至少粗略地近似于它们所代表的点之间的欧几里得距离。虽然它不会非常精确,但我相信你也无法做得更好。同时,即使在最好的情况下,我认为它对卷积代码的帮助也是极小的。
答案是否定的。想一想 - 内存是1D的,而你的矩阵是2D的。你想把那个额外的维度压缩进去 - 而且没有损失?这是不可能的。
更重要的是,一旦你离得足够远,它需要相同的时间加载到缓存中。如果你有一个缓存未命中,无论它距离多远都没关系。从根本上讲,除非你想为数组获取LRU,否则你无法获得比简单数组更连续/更好的性能。
我认为你忘记了计算机内存中的距离并不是由一台脚步运行的计算机CPU访问的 :),所以这种距离基本上是无关紧要的。
它是随机访问内存,因此您真正需要做的是找出需要执行哪些操作,并为此优化访问。
您需要将地址从内存空间重新转换为原始数组空间以完成此操作。此外,您仅强调距离可能仍会导致一些问题(没有方向)
如果我有一个R x C的数组,并且两个单元格位于位置 [r,c] 和 [c,r],则从某个任意点(比如 [0,0])的距离是相同的。除非您拥有那些新奇的量子位计算机,否则绝不可能使一个内存地址容纳两个东西。
然而,您可以考虑到在一个行主数组中,每行都是C * sizeof(yourdata)字节长。相反,您可以说数组范围内任何内存地址的原始坐标是
r =(address / C) c =(address%C)
所以
r1 =(address1 / C)
r2 =(address2 / C)
c1 =(address1%C)
c2 =(address2%C)
dx = r1-r2
dy = c1-c2
dist = sqrt(dx ^ 2 + dy ^ 2)
(这里假设你正在使用从零开始的数组) (将所有内容压缩在一起以使其运行更加高效)这与亲密度不完全相关,但可能会有所帮助。这对于最小化磁盘访问肯定有所帮助。
获取更好的“亲密度”的一种方法是将图像分块。如果您的卷积内核小于一个块的大小,则在最坏的情况下通常仅涉及到4个块。您可以递归地将块划分为更大的部分,以使本地化得到改善。类似斯托克斯(至少我认为是斯托克斯)的论点(或某些变分法)可以表明,对于矩形而言,最佳(指任意子矩形的审查)形状是相同长宽比的较小矩形。
快速直觉——想象一个正方形——如果您用小正方形平铺大正方形,则正方形包含给定周长的最大面积的事实意味着正方形平铺具有最小的边界长度。当您转换大正方形时,我认为您可以证明应该以相同的方式转换小块。(也可以进行简单的多元微分)
经典的例子是放大间谍卫星数据图像并进行卷积以增强的情况。如果您保留数据并返回它,则分块的额外计算确实很值得。
对于不同的压缩方案,例如余弦变换,这也非常有价值。(这就是为什么当您下载图像时,它经常以越来越小的正方形显示,直到达到最终分辨率的原因。
这个领域有很多书籍,它们非常有帮助。