为什么Scipy的KDTree如此缓慢？

Question

假设我有大约100组由100个点组成的数据集，并且想要找出哪些点在给定的距离范围内。我有两种实现方法，一种使用k-d树，另一种是简单地计算成对的距离：

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方法会更快，因为它不需要考虑每对可能的点。

那么，我理解错了什么，这个过程能否更快？

- TDN169

---

建立树是否意味着由于数据相对较小而无法分摊的开销过大？在“trees = ...”之后插入print(time.time() - start)以了解情况。 - gboffi

树的构建只需0.032秒。 - TDN169

Answer 1

这是纯Python实现的。而替代方案cKDTree则更快。

- ev-br

---

再次使用 cKDTree 测试我的代码，与 cdist 相比具有相同或更快的性能。谢谢！ - TDN169