효율적인 모든 것에 대한

Question

나는 3 차원 좌표의 3xN 배열을 가지고 있으며 모든 항목의 거리 행렬을 효율적으로 계산하고 싶습니다. 적용 할 수있는 중첩 루프가 아닌 효율적인 루프 전략이 있습니까?

현재 의사의 구현 :

for i,coord in enumerate(coords): 
    for j,coords2 in enumerate(coords): 
     if i != j: 
      dist[i,j] = numpy.norm(coord - coord2) 

Answer 1

정확하게 결과를 재현하기 :

>>> import scipy.spatial as sp 
>>> import numpy as np 
>>> a=np.random.rand(5,3) #Note this is the transpose of your array. 
>>> a 
array([[ 0.83921304, 0.72659404, 0.50434178], #0 
     [ 0.99883826, 0.91739731, 0.9435401 ], #1 
     [ 0.94327962, 0.57665875, 0.85853404], #2 
     [ 0.30053567, 0.44458829, 0.35677649], #3 
     [ 0.01345765, 0.49247883, 0.11496977]]) #4 
>>> sp.distance.cdist(a,a) 
array([[ 0.  , 0.50475862, 0.39845025, 0.62568048, 0.94249268], 
     [ 0.50475862, 0.  , 0.35554966, 1.02735895, 1.35575051], 
     [ 0.39845025, 0.35554966, 0.  , 0.82602847, 1.1935422 ], 
     [ 0.62568048, 1.02735895, 0.82602847, 0.  , 0.3783884 ], 
     [ 0.94249268, 1.35575051, 1.1935422 , 0.3783884 , 0.  ]]) 

이 중복 계산하지 않고 더 효율적으로 할 만의 고유 쌍을 계산하려면 :

>>> sp.distance.pdist(a) 
array([ 0.50475862, 0.39845025, 0.62568048, 0.94249268, 0.35554966, 
     1.02735895, 1.35575051, 0.82602847, 1.1935422 , 0.3783884 ]) 
#pairs: [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), 
#   (2, 4), (3, 4)] 

주 2 개의 배열의 관계 cdist 배열에 의해 재현 할 수 있습니다 :

>>> out=np.zeros((a.shape[0],a.shape[0])) 
>>> dists=sp.distance.pdist(a) 
>>> out[np.triu_indices(a.shape[0],1)]=dists 
>>> out+=out.T 

>>> out 
array([[ 0.  , 0.50475862, 0.39845025, 0.62568048, 0.94249268], 
     [ 0.50475862, 0.  , 0.35554966, 1.02735895, 1.35575051], 
     [ 0.39845025, 0.35554966, 0.  , 0.82602847, 1.1935422 ], 
     [ 0.62568048, 1.02735895, 0.82602847, 0.  , 0.3783884 ], 
     [ 0.94249268, 1.35575051, 1.1935422 , 0.3783884 , 0.  ]]) 

---

일부 다소 놀라운 timings-

셋업 :

def pdist_toarray(a): 
    out=np.zeros((a.shape[0],a.shape[0])) 
    dists=sp.distance.pdist(a) 

    out[np.triu_indices(a.shape[0],1)]=dists 
    return out+out.T 

def looping(a): 
    out=np.zeros((a.shape[0],a.shape[0])) 
    for i in xrange(a.shape[0]): 
     for j in xrange(a.shape[0]): 
      out[i,j]=np.linalg.norm(a[i]-a[j]) 
    return out 

타이밍 : 그래서 당신이 원하는 경우

arr=np.random.rand(1000,3) 

%timeit sp.distance.pdist(arr) 
100 loops, best of 3: 4.26 ms per loop 

%timeit sp.distance.cdist(arr,arr) 
100 loops, best of 3: 9.31 ms per loop 

%timeit pdist_toarray(arr) 
10 loops, best of 3: 66.2 ms per loop 

%timeit looping(arr) 
1 loops, best of 3: 16.7 s per loop 

사각 a 당신이 단지 pdist을 사용하기를 원한다면 당신은 cdist을 사용해야합니다. 루핑은 1000 요소가있는 배열의 경우 ~ 4000x 느리고 cdist 인 경우와 비교하여 10 요소가있는 배열의 경우 ~ 70x 느립니다.