scipy.spatial.ckdtree 运行慢慢来

Question

我一直在 scipy 中使用 spatial.cKDTree 来计算点之间的距离。对于我的典型数据集（查找 ~1000 点到 ~1e6 点数组的距离），它总是运行非常快（~1 秒）。

我在Ubuntu 14.10 的计算机上运行在python 2.7.6 中使用此代码。直到今天早上，我已经用 apt-get 管理了大多数 python 个包，包括 scipy 和 numpy。不过，我想要一些软件包的最新版本，所以我决定通过 apt-get 在 /usr/lib/python2.7/ 中安装软件包，并使用 pip install 重新安装所有软件包（注意 scipy 依赖项，如 liblapack-dev 和 apt-get，如有必要）。一切都已安装并且可以毫无问题地导入。

import scipy
import cython
scipy.__version__
'0.16.0'
cython.__version__
'0.22.1'

现在，运行宁 spatial.cKDTree 在相同大小的数据集上进行得非常慢。我看到运行时间约为 500 秒而不是 1 秒。我无法弄清楚发生了什么。

关于我在使用 pip 而不是 apt-get 安装过程中可能会导致 scipy.spatial.cKDTree 到运行如此缓慢的建议吗？

Answer 1

在 0.16.x 中，我添加了使用中值或滑动中点规则构建 cKDTree 的选项，以及选择是否重新计算 kd 树中每个节点的边界超矩形。默认值基于 scipy.spatial.cKDTree 和 sklearn.neighbors.KDTree 性能的经验。在某些人为的情况下（沿维度高度拉伸的数据）它可能会产生负面影响，但通常它应该更快。尝试用 balanced_tree=False and/or compact_nodes=False 构建 cKDTree。将两者都设置为 False 会得到与 0.15.x 相同的行为。不幸的是，很难设置让每个人都满意的默认值，因为性能取决于数据。

另请注意，在 balanced_tree=True 中，我们在构建 kd 树时通过快速选择计算中位数。如果由于某种原因对数据进行了预排序，则会非常慢。在这种情况下，这将有助于打乱输入数据的行。或者您可以设置 balanced_tree=False 以避免部分快速排序。

还有一个新选项可以对最近邻查询进行多线程处理。尝试用 n_jobs=-1 调用 query，看看是否对您有帮助。

2020 年 6 月更新： SciPy 1.5.0 将使用一种新算法（基于 introselect 的部分排序，来自 C++ STL）来解决此处报告的问题。

Answer 2

在 SciPy 的下一版本中，平衡的 kd 树将使用 introselect 而不是 quickselect 创建，这在结构化数据集上要快得多。如果您在图像或网格等结构化数据集上使用 cKDTree，您可以期待性能的重大提升。如果您从 GitHub 上的主分支构建 SciPy，它已经可用。

scipy.spatial.ckdtree 运行慢慢来

scipy.spatial.ckdtree running slowly

python

performance

scipy