python - scipy.spatial.KDTree 和 scipy.spatial.cKDTree 之间的区别

Question

这两种算法有什么区别？

Answer 1

cKDTree是 KDTree 的一个子集，用Cython包裹的 C++ 实现，因此速度更快。

他们每个人都是

一个二叉树，每个节点代表一个轴对齐的超矩形。每个节点指定一个轴，并根据它们沿该轴的坐标是否大于或小于特定值来拆分点集。

但是KDTree

还支持所有邻居查询，包括点数组和其他 kd 树。这些确实使用了相当有效的算法，但 kd-tree 不一定是此类计算的最佳数据结构。

Answer 2

在一个用例中（在 KDTree 中查找大约 100K 点的 5D 最近邻）cKDTree 比 KDTree 快 12 倍左右。

Answer 3

目前，两者都有几乎相同的 API，并且cKDTree比KDTree. 因此，在不久的将来，SciPy 开发人员计划删除KDTree，并将以向后兼容的方式cKDTree重命名为。KDTree

参考：详细的 SciPy 路线图 — SciPy v1.6.0.dev 参考指南 https://docs.scipy.org/doc/scipy/reference/roadmap-detailed.html#spatial