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

Question

我正在寻找的数据结构,让我来存储M-by- N值的2D矩阵连续在存储器中,以使得任意两个点之间的存储器的距离近似于所述基质的那些点之间的欧几里得距离.也就是说,在作为一维M * N元素阵列的典型行主表示中,存储器距离在相同行(1)中的相邻单元和相邻行()中的相邻单元之间不同N.

我想要一种减少或消除这种差异的数据结构.真的,这样一个结构的名称就足够了 - 我可以自己实现它.如果答案碰巧引用了这类文件的库,那也是可以接受的,但它们应该可以用于C++.

我有一个应用程序需要在没有硬件加速的情况下执行快速图像卷积,虽然我知道这种事情的常用优化技术,但我觉得专门的数据结构或数据排序可以提高性能.

Answer 1

我猜"不"!如果答案恰好是"是",那么它几乎肯定是如此不规则,以至于卷积型操作的速度会慢一些.

编辑

为了限定我的猜测,举一个例子.假设我们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-trees的建议).但是,它仍然需要不规则访问和指针追踪,因此对于任何给定数量的点,将比直接卷积慢得多.

Answer 2

鉴于要求您将值连续存储在内存中,我强烈建议您研究空间填充曲线,尤其是希尔伯特曲线.

为了给出一些上下文,有时在数据库索引中使用这样的曲线来改善多维范围查询的局部性(例如,"在该矩形中找到具有x/y坐标的所有项目"),从而旨在减少不同页面的数量.访问.有点类似于已经在这里建议的R树.

无论哪种方式,它看起来你被绑定到内存中的M*N数组值,所以整个问题是关于如何排列该数组中的值,我想.(除非我误解了这个问题.)

事实上,这样的排序可能仍然只会改变距离分布的特征.从矩阵中任意两个随机选择的点的平均距离不应该改变,所以我必须同意Oli.我想,潜在的好处在很大程度上取决于您的具体用例.

Answer 3

您可以查看空间填充曲线,特别是Z阶曲线,它(主要)保留空间局部性.然而,查找索引可能在计算上是昂贵的.

如果您正在使用它来尝试提高缓存性能,您可以尝试一种称为"bricking"的技术,这有点像空间填充曲线的一个或两个级别.基本上,您将矩阵细分为nxn tile(其中nxn整齐地适合您的L1缓存).您还可以存储另一级别的切片以适应更高级别的缓存.这对空间填充曲线的优势在于索引可以相当快地计算.这篇论文中包含一个参考文献:http://citeseerx.ist.psu.edu/viewdoc/summary？doi = 10.1.1.30.8959