scipy.spatial.KDTree和scipy.spatial.cKDTree的区别

Question

这两个算法有什么区别呢？

Answer 1

更新 2022：cKDTree 已被弃用

现在的 SciPy 文档说明，scipy.spatial.cKDTree 已经被弃用，取而代之的是功能完全相同的 scipy.spatial.KDTree。

这里有个说明：

cKDTree 和 KDTree 的功能是完全一样的。在 SciPy v1.6.0 之前，cKDTree 的性能更好，功能也稍有不同，但现在这两个名字只是为了兼容旧版本。如果你不需要和 SciPy 1.6 之前的版本兼容，建议使用 KDTree。

Answer 2

在一个实际应用中，比如在一个有大约10万个点的KD树里进行5维最近邻查找，cKDTree的速度大约比KDTree快12倍。

Answer 3

cKDTree 是 KDTree 的一个子集，它是用 C++ 实现的，并通过 Cython 包装，所以运行速度更快。

它们每一个都是

一种二叉树，每个节点代表一个轴对齐的超矩形。每个节点指定一个轴，并根据点在该轴上的坐标是大于还是小于某个特定值来划分点的集合。

但是 KDTree

还支持全邻居查询，可以处理点的数组和其他 kd-tree。这些查询使用了相对高效的算法，但 kd-tree 并不一定是进行这种计算的最佳数据结构。