这种数据结构存在吗?

13
我正在寻找一种数据结构,可以在内存中连续存储一个M乘N的2D值矩阵,使得任意两点之间在内存中的距离近似于在矩阵中这些点之间的欧几里得距离。即,在典型的按行主序列表示为一个M*N个元素的一维数组中,相邻单元格之间的内存距离在同一行中不同(1),在相邻行中也不同(N)。
我想要一个可以减少或消除这种差异的数据结构。实际上,只需要这种结构的名称,我自己就可以实现它。如果答案涉及到此类库,则也可接受,但它们应该能够与C ++一起使用。
我有一个需要快速执行图像卷积而无需硬件加速的应用程序,虽然我知道通常的优化技术可以完成这种事情,但我认为专门的数据结构或数据排序可能会提高性能。

1
@Martin:不,那正是他想避免的。 - Oliver Charlesworth
3
@Martin,@Oli:当然不是作业。我现在不上课,而且我的大学也从来没有布置过这么有用的作业。你们觉得我在哪里回答了自己的问题? - Jon Purdy
1
@Larry:非常好的观点。我认为任何拥有1840声望值的SO用户都不知道计算机的第一件事情。 - Ian Henry
7
@Larry:我暑假一直到9月初。你可以对我有任何想法,你认为是否正确完全由你自己决定。我不需要社区成员的认可,尤其是那些似乎不尊重我的人。我需要解决当前的问题,学习新知识,并享受编程带给我的乐趣,就像我一生中大部分时间所做的那样。让我们都保持文明。 - Jon Purdy
4
@Larry:我同意SO声望本身并不是可靠的能力指标。无论如何,由于内存和处理器之间的相互作用,当前计算机中的内存绝对不是真正的随机访问。编写糟糕的代码很容易导致几乎每个操作都发生缓存未命中,这可能会将性能降低一个数量级。这基本上是一种优化问题,认为问题本身暴露出我在计算方面存在某种基本误解的想法简直荒谬。 - Jon Purdy
显示剩余3条评论
10个回答

7
我猜“不行”!如果答案是“是”,那么它几乎肯定是如此不规则,以至于进行卷积类型操作会更慢。
编辑
为了证明我的猜测,举个例子。假设我们首先存储a[0][0]。我们希望a[k][0]和a[0][k]之间的距离相似,并且与k成比例,因此我们可能选择交错存储第一行和第一列(即a[0][0],a[1][0],a[0][1],a[2][0],a[0][2]等)。但是现在我们该如何处理例如a[1][0]?所有靠近它的内存位置现在都被靠近a[0][0]的东西占据了。
虽然还有其他可能性,但我敢打赌你总是会遇到这种问题。
编辑
如果您的数据是稀疏的,则可能有机会做一些聪明的事情(例如Cubbi提出的R树)。但是,它仍然需要不规则访问和指针追踪,因此对于任何给定数量的点,它将比直接卷积慢得多。

7
给定要求,您希望在内存中连续存储值,我强烈建议您研究填充曲线,特别是Hilbert曲线。为了提供一些背景,这样的曲线有时用于数据库索引中,以改善多维范围查询(例如,“查找此矩形中具有x / y坐标的所有项目”)的局部性,从而旨在减少不同页面的访问数量。与已经在此处建议的R树有点相似。无论如何,看起来您必须将值绑定到内存中的M * N数组上,因此整个问题都是关于如何排列该数组中的值,我想。(除非我误解了问题。)因此,实际上,这种排序可能仍然只会改变距离分布的特征...从矩阵中任意选择两个点的平均距离不应更改,因此我必须在那里同意Oli。潜在的好处在很大程度上取决于您的具体用例,我想。

我刚刚看到了Hilbert曲线的文章。看起来这可能正是我需要的。你说得对,问题在于排序,而不是数据结构本身。我在想转换成和从Hilbert排序会不会太慢,但对于我的应用程序来说,卷积本身的速度更重要。我会进行实验。 - Jon Purdy
您可能不需要完整的希尔伯特曲线。通过比特交错,您可以获得大部分好处(这可以通过使用坐标查找表并将结果合并进行操作)。另外,无论使用哪种曲线,注意您可以利用新的空间相干性来使用排序:按曲线顺序遍历数组比使用原始行顺序更好地利用缓存。 - comingstorm
同意ig2r的编辑。对于每个你移动到正确距离的坐标,你又把另一个坐标变成了错误的坐标。虽然我理解空间填充曲线在数据索引等方面的用途(其中你只需寻找高概率的局部性),但是在卷积等情况下,访问模式是确定的。但如果你确实发现了改进,我会很感兴趣听听的(卷积是我经常做的事情!)。 - Oliver Charlesworth

6
您可以考虑使用空间填充曲线,特别是Z顺序曲线,它(大多数情况下)保留了空间局部性。但查找索引可能会计算成本高昂。
如果您要尝试提高缓存性能,可以尝试一种称为“砖块化”的技术,它有点像一到两级的空间填充曲线。基本上,您将矩阵细分为n×n的瓷砖(其中n×n正好适合您的L1缓存)。您还可以存储另一层瓷砖以适应更高级别的缓存。与空间填充曲线相比,它的优势在于索引可以相对快速地计算。本文中包含一篇参考资料:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8959

第一次听说变砖,你得爱上这个网站...谢谢Matthew! - Matthieu M.

3
这似乎可以通过使用R树或其变种来解决。C++标准库中没有类似的东西,但是看起来在boost候选库Boost.Geometry中有一个R树(尚未成为boost的一部分)。在编写自己的代码之前,建议先查看该库。

+1 链接到 R 树,这让我了解了希尔伯特 R 树,进而引入了希尔伯特排序。 - Jon Purdy

3
无法将二维结构“线性化”为一维结构并在两个方向上保持邻近关系不变。这是世界的基本拓扑属性之一。
尽管如此,通常用于2D数组表示的标准行优先或列优先存储顺序在需要尽可能保留邻近性时并不是最佳选择。通过使用各种分形曲线(填充空间曲线)的离散逼近,可以获得更好的结果。
Z-order曲线是这种应用中的一种流行方法:http://en.wikipedia.org/wiki/Z-order_(curve) 请记住,无论使用哪种方法,总会存在违反距离要求的元素。

谢谢提供链接。我知道完全保留元素之间的接近关系是不可能的,但我只是希望在平均情况下和相对较大的输入中有所改善。 - Jon Purdy

1

你可以将你的二维矩阵想象成一个大螺旋,从中心开始向外扩展。展开这个螺旋,并按照这个顺序存储数据,地址之间的距离至少粗略地近似于它们所代表的点之间的欧几里得距离。虽然它不会非常精确,但我相信你也无法做得更好。同时,即使在最好的情况下,我认为它对卷积代码的帮助也是极小的。


1

答案是否定的。想一想 - 内存是1D的,而你的矩阵是2D的。你想把那个额外的维度压缩进去 - 而且没有损失?这是不可能的。

更重要的是,一旦你离得足够远,它需要相同的时间加载到缓存中。如果你有一个缓存未命中,无论它距离多远都没关系。从根本上讲,除非你想为数组获取LRU,否则你无法获得比简单数组更连续/更好的性能。


但是,如果CPU要从一个内存位置走到另一个内存位置太远了,它可能会感到疲倦,这不会减缓它的速度吗?开玩笑的。 - Larry Watanabe

0

我认为你忘记了计算机内存中的距离并不是由一台脚步运行的计算机CPU访问的 :),所以这种距离基本上是无关紧要的。

它是随机访问内存,因此您真正需要做的是找出需要执行哪些操作,并为此优化访问。


0

您需要将地址从内存空间重新转换为原始数组空间以完成此操作。此外,您仅强调距离可能仍会导致一些问题(没有方向)

如果我有一个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)

(这里假设你正在使用从零开始的数组) (将所有内容压缩在一起以使其运行更加高效)
要获取更多想法,请查找任何使用名为“步幅”的计算值的2D图像处理代码,该值基本上是指它们在内存地址和数组地址之间来回跳跃的指示器。

0

这与亲密度不完全相关,但可能会有所帮助。这对于最小化磁盘访问肯定有所帮助。

获取更好的“亲密度”的一种方法是将图像分块。如果您的卷积内核小于一个块的大小,则在最坏的情况下通常仅涉及到4个块。您可以递归地将块划分为更大的部分,以使本地化得到改善。类似斯托克斯(至少我认为是斯托克斯)的论点(或某些变分法)可以表明,对于矩形而言,最佳(指任意子矩形的审查)形状是相同长宽比的较小矩形。

快速直觉——想象一个正方形——如果您用小正方形平铺大正方形,则正方形包含给定周长的最大面积的事实意味着正方形平铺具有最小的边界长度。当您转换大正方形时,我认为您可以证明应该以相同的方式转换小块。(也可以进行简单的多元微分)

经典的例子是放大间谍卫星数据图像并进行卷积以增强的情况。如果您保留数据并返回它,则分块的额外计算确实很值得。

对于不同的压缩方案,例如余弦变换,这也非常有价值。(这就是为什么当您下载图像时,它经常以越来越小的正方形显示,直到达到最终分辨率的原因。

这个领域有很多书籍,它们非常有帮助。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接