scipy.spatial.ckdtree 运行缓慢

Question

scipy.spatial.ckdtree 运行缓慢

3

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

我在Ubuntu 14.10上的计算机上运行这段代码，使用的是Python 2.7.6。直到今天早上，我大多数Python包都是用apt-get管理的，包括scipy和numpy。但我想要最新版本的几个包，所以我决定卸载由apt-get安装在/usr/lib/python2.7/中的包，并使用pip install重新安装所有包（如有必要，使用apt-get处理scipy依赖项，如liblapack-dev）。所有的包都已经安装好了，可以顺利导入。

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

现在，对于相同大小的数据集运行spatial.cKDTree速度非常慢。我看到的运行时间约为500秒，而不是1秒。我很难弄清楚出了什么问题。

有什么建议可以解释为什么使用pip安装而不是apt-get导致scipy.spatial.cKDTree运行如此缓慢吗？

- jdmcbr

2个回答

1

在下一个SciPy版本中，使用introselect而不是quickselect创建平衡kd树，在结构化数据集上速度更快。如果您在结构化数据集（如图像或网格）上使用cKDTree，则可以期待性能大幅提升。如果您从GitHub的主分支构建SciPy，则已经可以使用它。

- Sturla Molden

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sturla Molden · Accepted Answer

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

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

还有一个新选项可以对最近邻查询进行多线程处理。尝试使用n_jobs=-1调用query，看看它是否对您有所帮助。 2020年6月更新： SciPy1.5.0将使用一种新算法（基于C++ STL的introselect部分排序），解决了这里报告的问题。