caching - 二维缓存友好的数据结构和空间填充曲线

Question

我读过诸如Peano曲线之类的空间填充曲线对于在线性地址空间中维护缓存友好的数据结构很有用，因为它们维护了物理空间局部性。

但是，我不确定如何实际使用它们。这些曲线中是否有任何公式可以将线性地址快速转换为 (x,y) 坐标，反之亦然？否则，当查找某对坐标时，如何确定在内存中查找的位置？一个例子会很有帮助。

Answer 1

如评论中所述，将坐标转换为二进制并将其交错。如果您想要四键，则将其视为以 4 为基数的数字。