java - 希尔伯特按分而治之排序算法？

我正在尝试按希尔伯特顺序对d维数据 vector 进行排序，以批量加载空间索引。

但是，我不想显式地为每个点计算希尔伯特值，这尤其需要设置特定的精度。在高维数据中，这涉及到诸如32*d位之类的精度，很难有效地进行处理。当数据分布不均匀时，其中一些计算是不必要的，并且数据集的某些部分需要额外的精度。

相反，我正在尝试执行分区方法。当您查看2D一阶希尔伯特曲线时

1   4
|   |
2---3

我首先沿x轴拆分了数据，以便第一部分(不一定包含对象的一半!)将由1和2组成(尚未排序)，第二部分将包含3和4的对象只要。接下来，我在Y轴上再次将每一半分割，但将顺序反转为3-4。

因此，从本质上讲，我想执行分而治之的策略(与QuickSort密切相关-在均匀分布的数据上这甚至是最佳选择!)，并且仅根据需要计算希尔伯特索引的必要“位”。因此，假设在“1”中只有一个对象，则无需计算它的完整表示形式；如果对象均匀分布，分区大小将 swift 减小。

我确实知道通常的教科书方法可以转换为长的，灰度编码的尺寸交织。这不是我想要的(有很多可用的示例)。我明确地只想要一个懒惰的分而治之排序。另外，我需要的不仅仅是2D。

有谁知道以这种方式工作的文章或希尔伯特排序算法？或者是一个关键点，如何正确选择“轮换”，为此选择哪种表示形式？尤其是在高维中……在2D中，这是微不足道的。 1旋转+ y，+ x，而4旋转-y，-x(旋转和翻转)。但我想，在更高维度上，这变得更加棘手。

(结果当然应该与立即按足够大的精度按希尔伯特顺序对对象进行排序时相同；我只是想节省不必要的时间来计算完整表示，而不得不对其进行管理。许多人们会保留一个非常昂贵的哈希图“对象到希尔伯特数”。)

对于Peano曲线和Z曲线，应该可以使用类似的方法，并且可能更容易实现...我可能应该首先尝试使用这些方法(Z曲线已经在工作-实际上可以归结为类似于QuickSort的东西，使用适当的均值/网格值作为虚拟枢轴，并在每次迭代中遍历维度)。

编辑:有关如何解决Z和Peano曲线的信息，请参见下文。它也已经适用于2D Hilbert曲线。但是我还没有希尔伯特曲线的旋转和反演。

最佳答案

使用radix sort。将每个一维索引拆分为d .. 32部分，每个部分的1 .. 32/d位大小。然后(从高位到低位)为每个索引块计算其希尔伯特值，并将对象随机排列到适当的bin中。

这对于希尔伯特顺序或Z顺序的均匀和不均匀分布的数据都应适用。无需多精度计算。

有关将索引片段转换为希尔伯特顺序的一个细节:

首先提取必要的位

然后从各个维度交错位

然后将一维索引转换为反格雷码。

如果索引以 double 形式存储:

如果索引可能为负，请添加一些值以使所有内容均为正，从而简化任务。

确定2的最小整数幂，大于2的所有索引并将所有索引除以该值

将索引乘以2 ^(当前排序步骤所需的位数)。
截断结果，将其转换为整数，并将其用于希尔伯特排序(交织并计算逆格雷码)

从索引中减去上一步截断的结果:index = index - i

关于您的基数排序的变体，我建议使用两个大小为d的二进制数组(一个主要用作堆栈，另一个用于反转索引位)和旋转值来扩展zsort(以使hilbertsort脱离zsort) (用于重新排列尺寸)。

如果堆栈中的最高值是1，则将pivotize(... ascending)更改为pivotize(...... dending)，然后对于递归的第一部分，将此最高值压入堆栈，第二个则将其压入堆栈此值的倒数。每次递归后都应还原此堆栈。它包含基数排序过程的最后d递归的“决策树”(逆格雷码)。

在d递归之后，应使用此“决策树”堆栈来重新计算旋转值和反转数组。确切的方法是不平凡的。可以在以下链接中找到它:hilbert.c或hilbert.c。

关于java - 希尔伯特按分而治之排序算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8459562/