为什么Scipy的KDTree这么慢？

Question

假设我有大约100组100分,并想知道哪些点在彼此的给定距离内.我有两个这样的实现,一个使用kd树,另一个只是成对距离:

from scipy.spatial.distance import cdist
from scipy.spatial import KDTree
from itertools import combinations
import numpy
import time

pts = [numpy.random.randn(100,2) for x in range(100)]


start = time.time()

for p1, p2 in combinations(pts,2):
    numpy.argwhere(cdist(p1, p2) < 0.5)

print(time.time() - start)


start = time.time()

trees = [KDTree(x) for x in pts]

for p1, p2 in combinations(trees,2):
    p1.query_ball_tree(p2,0.5,eps=1)

print(time.time() - start)

我的机器cdist需要0.5秒,而KDTree实施需要一分钟.构建树需要0.03秒.我希望该KDTree方法更快,因为它不需要考虑每一对可能的点.

那么,我误解了什么,这可以更快地完成吗？

Answer 1

这是纯粹的蟒蛇.替代实现cKDTree要快得多.