我一直在读一些关于morton代码的东西,我得到局部性是保留在生成的数字序列中。
我不明白的是如何使用这些信息来压缩数据或有效地并行构建数据。
来源:http://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/
Morton排序本身与数据压缩没有内在联系。它只是在内存中布局空间数据的一种方式,使得对连续空间块的查询倾向于映射到连续的内存块,从而获得良好的缓存效率。
在你引用的链接中引用的算法论文中,Morton order被用来提高磁盘读取的效率&写道。
该算法将复杂的三角形网格转换为高分辨率体素中间表示(以Morton顺序存储),然后将该表示转换为稀疏(压缩)输出形式。
Morton阶的一个性质是它与深度优先遍历八叉树(或二维四叉树)的顺序相匹配。这样可以方便地在输出八叉树数据结构和中间数据结构之间进行对齐。因此,在输出八叉树中构造一个节点需要来自中间结构中一组连续索引的数据。这使得算法在给定的步骤中只读取它需要的数据,保持低内存占用和高缓存效率。
所以这里的Morton排序本身没有提供特别的压缩或并行化优势-你可以编写一个等效的算法,具有相同的压缩输出,在其中间使用线性排序,但是它的写入和读取将更加分散,因此它可能不会处理数据快。
但是如果你使用四叉树或八叉树来压缩数据,Morton排序可以使你的数据索引更干净,性能更高。