bbt*_*trb 7 algorithm nearest-neighbor spatial-index z-order-curve
在研究粒子相互作用的模拟时,我偶然发现Morton-order(Z-order)(维基百科链接)中的网格索引,这被认为是提供有效的最近邻细胞搜索.我读过的主要原因是内存中空间紧密单元的几乎顺序排序.
处于第一个实现的中间,我无法围绕如何有效地实现最近邻居的算法,特别是与基本的统一网格相比.
给定单元(x,y),获得8个相邻单元索引并计算相应的z索引是微不足道的.虽然这为元素提供了恒定的访问时间,但是要在预定义的表中计算或查找z-index(对于每个轴和OR'ing分开).这怎么可能更有效率？是否正确,按顺序访问数组A中的元素说A [0] - > A 1 - > A [3] - > A [4] - > ...比A顺序更有效[1023] ] - > A [12] - > A [456] - > A [56] - > ......？
我预计存在一种更简单的算法来查找z次序中的最近邻居.顺便说一句:找到邻居的第一个单元格,迭代.但这不可能是真的,因为这只能在2 ^ 4大小的块内很好地工作.然而,存在两个问题:当小区不在边界上时,可以容易地确定该块的第一个小区并且遍历该块中的小区,但是必须检查该小区是否是最近邻居.当细胞位于边界上时,情况更糟,而不是必须考虑2 ^ 5个细胞.我在这里错过了什么？是否有一个相对简单而有效的算法可以满足我的需求？
第1点中的问题很容易测试,但我不太熟悉所描述的访问模式生成的基本指令,并且非常希望了解幕后发生的事情.
在此先感谢任何帮助,参考等...
关于第2点:我应该补充一点,我理解如何为R ^ d中的点云构建Morton有序数组,其中索引i = f(x1,x2,...,xd)是从逐位交织等获得的.我试图理解的是,是否有比下面的天真ansatz更好的方法来获得最近的邻居(这里是d = 2,"伪代码"):
// Get the z-indices of cells adjacent to the cell containing (x, y)
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2
point = (x, y)
zindex = f(x, y)
(zx, zy) = f^(-1)(zindex) // grid coordinates
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1), // neighbor grid
(zx , zy - 1), (zx, zy + 1), // coordinates
(zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]
ni= [f(x[0], x[1]) for x in nc] // neighbor indices
在现代的基于多级缓存的计算机系统中,空间局部性是优化数据元素访问时间的重要因素.
简而言之,这意味着如果您访问内存中的数据元素,那么访问附近的内存中的另一个数据元素(具有接近第一个的地址)可以比访问数据元素更便宜几个数量级.远处.
当顺序访问1-d数据时,如在简单的图像处理或声音处理中,或者以相同的方式迭代处理每个元素的数据结构,然后按顺序将数据元素排列在存储器中往往实现空间局部性 - 即,因为您访问元素在访问元素N之后的N + 1,这两个元素应该在内存中彼此相邻放置.
标准c数组(以及许多其他数据结构)具有此属性.
莫顿排序的一点是要支持在数据访问方案2维的,而不是一个尺寸.换句话说,在访问元素(x,y)之后,您可以继续访问(x + 1,y)或(x,y + 1)或类似的.
莫顿排序意味着(x,y),(x + 1,y)和(x,y + 1)在存储器中彼此接近.在标准的c多维数组中,不一定是这种情况.例如,在数组myArray [10000] [10000]中,(x,y)和(x,y + 1)相距10000个元素 - 相隔太远以利用空间局部性.
在Morton排序中,标准c数组仍然可以用作数据的存储,但计算出(x,y)所在位置的计算不再像存储[x + y*rowsize]那么简单.
要使用Morton排序实现您的应用程序,您需要弄清楚如何将坐标(x,y)转换为商店中的地址.换句话说,您需要一个f(x,y)可用于访问商店的功能store[f(x,y)].
看起来你需要做更多的研究 - 按照维基百科页面上的链接,特别是BIGMIN功能上的链接.