performance - 平衡 KD 树 : Which approach is more efficient?

Question

我正在尝试使用 KD 树平衡一组(百万以上)3D 点，我有两种方法可以做到这一点。

方式一:

1. 使用 O(n) 算法找到沿给定轴的数组大小/第 2 大元素并将其存储在当前节点

2. 遍历向量中的所有元素，并针对每个元素，将它们与我刚刚找到的元素进行比较，并将较小的元素放入 newArray1，将较大的元素放入 newArray2

3. 递归

方式二:

1. 使用快速排序 O(nlogn) 沿给定轴对数组中的所有元素进行排序，取出位置 arraysize/2 的元素并将其存储在当前节点中。

2. 然后将索引0到arraysize/2-1的所有元素放入newArray1，将arraysize/2到arraysize-1的元素放入newArray2

3. 递归

方法 2 似乎更“优雅”，但方法 1 似乎更快，因为中值搜索和迭代都是 O(n)，所以我得到 O(2n)，它只是减少到 O(n)。但是同时，虽然方式2是O(nlogn)的时间来排序，但是把数组拆分成2可以在常数时间内完成，但是是否弥补了O(nlogn)的排序时间呢？

我该怎么办？还是有我什至没有看到的更好的方法来做到这一点？

Answer 1

方式三如何:

1. 使用诸如 QuickSelect 之类的 O(n) 算法来确保位置 length/2 处的元素是正确的元素，之前的所有元素都小于它，而之后的所有元素都大于它(无需对它们进行完全排序! ) - 这可能是您在方法 1 的第 1 步中使用的算法...

2. 递归到每一半(中间元素除外)并重复下一个轴。

请注意，您实际上不需要制作“节点”对象。您实际上可以将树保存在一个大数组中。搜索时，从第一个轴的 length/2 开始。

我已经看到 ELKI 使用了这个技巧。它使用非常少的内存和代码，这使得树非常快。