algorithm - 使用 Morton 顺序进行最近邻搜索的好处？

Question

在模拟粒子相互作用时，我偶然发现了 Morton 顺序(Z 顺序)( Wikipedia link ) 中的网格索引，它被认为可以提供高效的最近邻单元格搜索。我读过的主要原因是内存中空间上接近的单元格几乎按顺序排序。

在第一次实现过程中，我无法全神贯注地思考如何有效地实现最近邻算法，尤其是与基本均匀网格相比。

1. 给定一个单元格 (x,y)，获取 8 个相邻单元格索引并计算相应的 z-index 是微不足道的。虽然这提供了对元素的恒定访问时间，但必须计算或在预定义表中查找 z-index(每个轴和 OR'ing 分开)。这怎么可能更有效率？确实如此，按照 A[0] -> A 1 -> A[3] -> A[4] -> ... 的顺序访问数组 A 中的元素比 A[1023 ] -> A[12] -> A[456] -> A[56] -> ...?

2. 我期望存在一种更简单的算法来按 z 顺序查找最近的邻居。沿线的东西:找到邻居的第一个单元格，迭代。但这不可能是真的，因为这只适用于 2^4 大小的 block 。但是有两个问题:当单元格不在边界上时，可以很容易地确定 block 的第一个单元格并遍历 block 中的单元格，但必须检查单元格是否是最近邻。当单元格位于边界上时，情况更糟，而不是必须考虑 2^5 个单元格。我在这里错过了什么？有没有一种相对简单高效的算法可以满足我的需求？

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

在此先感谢您提供的任何帮助、引用等...

---

编辑:
感谢您澄清第 1 点!因此，使用 Z 排序，相邻单元的缓存命中率平均增加，这很有趣。有没有办法分析缓存命中率/未命中率？

关于第 2 点:我应该补充一点，我了解如何为 R^d 中的点云构建莫顿有序数组，其中索引 i = f(x1, x2, ..., xd) 是从按位交错等获得的。我尝试做的理解的是是否有比以下天真的答案更好的方法来获得最近的邻居(这里是 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

Answer 1

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

简单地说，这意味着如果您访问内存中的一个数据元素，那么访问附近内存中的另一个数据元素(具有接近第一个地址的地址)可以比访问一个数据便宜几个数量级远的元素。

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

标准 c 数组(和许多其他数据结构)具有此属性。

Morton 排序的要点是支持以二维 而非一维 维度访问数据的方案。换句话说，在访问元素 (x,y) 之后，您可以继续访问 (x+1,y) 或 (x,y+1) 或类似内容。

Morton 顺序意味着 (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 上的链接功能。