なぜScipyのKDTreeが遅いのですか？

Question

私は約100点のセットを持っていて、どの点が互いの所与の距離内にあるかを知りたいとしましょう。 KDTree実装が全体分かかりながら、私のマシン上でcdist

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) 

は0.5秒かかります：私は、2つの実装、1 kd木を使用し、その他単に取得ペアごとの距離を持っています。樹木の建設には0.03秒かかります。私はKDTreeメソッドがより速くなることを期待します。なぜなら、可能なすべての点のペアを考慮する必要がないからです。

私は誤解したことがあります。これはもっと速くできますか？

Answer 1

純粋なpythonです。代わりの実装であるcKDTreeははるかに高速です。