是否有具有这些特征的数据结构?

考虑到需要在内存中连续存储这些值,我强烈建议您进行研究 space-filling curves Hilbert curves .

为了提供一点上下文信息,有时在数据库索引中使用这种曲线来改进多维范围查询的局部性(例如,“在这个矩形中查找具有x/y坐标的所有项”),从而减少访问的不同页面的数量。有点类似于这里已经提出的R-树。

不管是哪种方式,看起来您绑定到了内存中的一个M*N值数组,所以整个问题是如何在该数组中排列值,我想。(除非我误解了这个问题。)

编辑

为了证实我的猜测,举个例子。假设我们储存 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] .

编辑

您可以查看空间填充曲线,特别是Z阶曲线,它(大部分)保留了空间局部性。然而,查找索引的计算成本可能会很高。

如果您正在使用它来尝试提高缓存性能,那么可以尝试一种称为“bricking”的技术,这有点像一个或两个级别的空间填充曲线。本质上,您可以将矩阵细分为nxn块(其中nxn正好适合一级缓存)。您还可以存储另一级别的磁贴以适合更高级别的缓存。与空间填充曲线相比,这种方法的优点是指数的计算速度相当快。本文包括一个参考文献: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8959

R-tree. 或者它的一个变种。在C++标准库中没有类似的东西,但是看起来好像在升压候选库中有一棵R树。 Boost.Geometry (还不是boost的一部分)。在写我自己的之前我会先看一看。

不可能将二维结构“线性化”为一维结构,并且在两个方向上保持接近关系不变。这是世界的基本拓扑性质之一。

http://en.wikipedia.org/wiki/Z-order_(curve)

但请记住,无论您使用哪种方法,总会有一些元素违反您的距离要求。

你可以把你的2D矩阵想象成一个大的螺旋,从中心开始,一直延伸到外面。展开螺旋,并按顺序存储数据,地址之间的距离至少为 模糊地 近似于它们所代表的点之间的欧氏距离。虽然不太准确,但我敢肯定你也不能做得更好。同时,我认为即使在最好的情况下,它对卷积码的帮助也很小。

答案是否定的。想想看-记忆是一维的。你的矩阵是二维的。你想在没有损失的情况下挤压额外的维度吗?这不会发生的。

更重要的是,一旦你走了一段距离,就需要同样的时间来加载到缓存中。如果你有一个缓存未命中,不管是100或100000。从根本上说,除非您想为您的阵列获得一个LRU,否则您无法获得比简单阵列更连续/更好的性能。

我想你忘了,计算机内存中的距离不是由步行运行的计算机cpu访问的:)所以距离几乎是不相关的。

它是随机存取存储器,所以实际上你必须弄清楚你需要做什么操作,并为此优化存取。

如果我有一个rxc的数组,在[R,C]和[C,R]的位置有两个单元格,那么到任意点的距离,比如说[0,0]是相同的。你不可能让一个内存地址包含两个东西,除非你有一台新的量子机器。

但是,您可以考虑在rxc的行主数组中,每行的长度是C*sizeof(yourdata)字节。相反,可以说数组边界内任何内存地址的原始坐标是

所以

c1=(地址1%C)

c2=(地址2%C)

dx=r1-r2

距离=sqrt(dx^2+dy^2)

(将所有这些压在一起,使其运行更优化)

这里有更多的想法,可以找到任何2D图像处理代码,它使用一个叫做“跨距”的计算值,这基本上是一个指示它们在内存地址和数组地址之间来回跳跃的指标

这与亲密度无关,但可能会有所帮助。它当然有助于最小化磁盘访问。

快速直觉-想想一个正方形-如果你用较小的正方形平铺较大的正方形,那么一个正方形在给定的周长内包围了最大的面积这一事实意味着正方形平铺的边界长度最小。当你变换大正方形的时候,我想你可以用同样的方法来显示你应该变换瓷砖。(也可以做一个简单的多元微分)

典型的例子是放大间谍卫星数据图像并进行卷积增强。如果您保留数据并返回,那么平铺的额外计算是非常值得的。

对于不同的压缩方案,如余弦变换,它也是非常值得的。(这就是为什么当你下载一个图像时,它经常出现在越来越小的方格中,直到达到最终的分辨率。

这方面有很多书,很有帮助。