使用莫顿阶进行最近邻搜索的好处？

在模拟粒子相互作用时，我偶然发现了莫顿阶（Z 阶）中的网格索引（维基百科链接 http://en.wikipedia.org/wiki/Z-order_%28curve%29）被认为提供了有效的最近邻小区搜索。我读到的主要原因是内存中空间上接近的单元几乎按顺序排列。

在第一次实现的过程中，我无法理解如何有效地实现最近邻居的算法，特别是与基本的统一网格相比。

1. 给定一个单元格 (x,y)，获取 8 个相邻单元格索引并计算相应的 z 索引很简单。尽管这提供了对元素的恒定访问时间，但必须计算 z-index 或在预定义表中查找（每个轴和 OR'ing 是分开的）。这怎么可能更有效率呢？按 A[0] -> A 的顺序访问数组 A 中的元素是真的吗1 http://en.wikipedia.org/wiki/Z-order_%28curve%29-> A[3] -> A[4] -> ... 比 A[1023] -> A[12] -> A[456] -> A[56] -> .. 的顺序更有效.?

2. 我期望存在一种更简单的算法来查找 z 顺序中的最近邻居。大致意思是：找到邻居的第一个单元格，迭代。但这不可能是真的，因为这只能在 2^4 大小的块内有效。然而，存在两个问题：当单元格不在边界上时，我们可以轻松确定块的第一个单元格并迭代块中的单元格，但必须检查该单元格是否是最近邻居。当单元位于边界上时，情况会更糟，必须考虑 2^5 个单元。我在这里缺少什么？是否有一种相对简单且有效的算法可以满足我的需要？

第 1 点中的问题很容易测试，但我不太熟悉所描述的访问模式生成的底层指令，并且真的很想了解幕后发生的事情。

预先感谢您提供任何帮助、参考资料等...

---

EDIT:
Thank you for clarifying point 1! So, with Z-ordering, the cache hit rate is increased on average for neighbor cells, interesting. Is there a way to profile cache hit/miss rates?

关于第2点： 我应该补充一点，我了解如何为 R^d 中的点云构建莫顿有序数组，其中索引 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

在现代基于多级缓存的计算机系统中，空间局部性是优化数据元素访问时间的重要因素。

简而言之，这意味着如果您访问内存中的一个数据元素，那么访问内存中附近的另一个数据元素（具有接近第一个地址的地址）可能比访问内存中的数据元素便宜几个数量级。离这很远。

当按顺序访问一维数据时，例如简单的图像处理或声音处理，或者以相同的方式迭代处理每个元素的数据结构，然后按顺序排列内存中的数据元素往往会实现空间局部性 - 即，因为您访问元素N+1 在访问元素 N 后，这两个元素应该在内存中相邻放置。

标准 C 数组（以及许多其他数据结构）具有此属性。

Morton 排序的要点是支持访问数据的方案two维度上代替one维度上。换句话说，在访问元素 (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) 的位置不再像 store[x+y*rowsize] 那么简单。

要使用 Morton 订购实现您的应用程序，您需要弄清楚如何将坐标 (x,y) 转换为商店中的地址。换句话说，你需要一个函数f(x,y)可用于访问商店，如下所示store[f(x,y)].

看起来您需要做更多研究 - 请点击维基百科页面上的链接，尤其是BIGMIN功能。