2D缓存友好的数据结构和空格填充曲线 [英] 2D cache-friendly data structures and space-filling curves

问题描述

我已经阅读了空格填充曲线，如 Peano曲线，可用于维护缓存友好的数据结构在线性地址空间，因为它们保持物理空间局部性。

I've read that space-filling curves such as the Peano curve are useful for maintaining cache-friendly data structures in a linear address space, since they maintain physical spatial locality.

但是，我不知道如何实际使用它们。任何这些曲线都有公式用于快速将线性地址转换为（x，y）坐标，反之亦然？否则，当查找一对坐标时，如何确定内存中的外观？一个例子将是非常有帮助的。

However, I'm not sure how to actually use them. Do any of these curves have formulas for quickly translating a linear address into (x,y) coordinates and vice-versa? Otherwise, how do I determine where in memory to look when looking up a certain pair of coordinates? An example would be very helpful.

推荐答案

正如在注释中所述，将坐标转换为二进制并交错。如果你想要一个四键，那么把它当成一个基数4。

As stated in the comment translate the co-ordinate to a binary and interleave it. Then treat it a base-4 number if you want a quadkey.

这篇关于2D缓存友好的数据结构和空格填充曲线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！