[PYTHON] 파이썬에서 가장 빠른 pairwise distance metric

파이썬에서 가장 빠른 pairwise distance metric

나는 1D 배열의 숫자를 가지고 있으며 모든 쌍의 유클리드 거리를 계산하려고합니다. 나는 방송으로 이것을하는 방법 (SO 덕분에)을 가지고 있지만, 각 거리를 두 번 계산하기 때문에 비효율적이다. 그리고 그것은 잘 확장되지 않습니다.

다음은 1000 개의 숫자 배열로 원하는 것을 제공하는 예제입니다.

import numpy as np
import random
r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
dists = np.abs(r - r[:, None])

scipy / numpy / scikit-learn에서 가장 빠른 구현은 무엇입니까? 1D 배열의 크기가 10k를 초과하는 상황에서 확장이 가능하다면이 방법을 사용할 수 있습니다.

참고 : 행렬은 대칭이므로 적어도 2x 속도 향상을 얻는 것이 가능하다는 것을 짐작할 수 있습니다.

해결법

1. ==============================

   1.다른 답변들도 질문에 답을하지 않았습니다. 1 개는 Cython에서, 1 개는 더 느립니다. 그러나 둘 다 매우 유용한 힌트를 제공했습니다. 그것들에 뒤이어서 scipy.spatial.distance.pdist가 갈 길이라고 제안한다.

   다른 답변들도 질문에 답을하지 않았습니다. 1 개는 Cython에서, 1 개는 더 느립니다. 그러나 둘 다 매우 유용한 힌트를 제공했습니다. 그것들에 뒤이어서 scipy.spatial.distance.pdist가 갈 길이라고 제안한다.

   여기에 몇 가지 코드가 있습니다.

   import numpy as np
   import random
   import sklearn.metrics.pairwise
   import scipy.spatial.distance
   
   r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
   c = r[:, None]
   
   def option1(r):
       dists = np.abs(r - r[:, None])
   
   def option2(r):
       dists = scipy.spatial.distance.pdist(r, 'cityblock')
   
   def option3(r):
       dists = sklearn.metrics.pairwise.manhattan_distances(r)
   

   IPython으로 타이밍하기 :

   In [36]: timeit option1(r)
   100 loops, best of 3: 5.31 ms per loop
   
   In [37]: timeit option2(c)
   1000 loops, best of 3: 1.84 ms per loop
   
   In [38]: timeit option3(c)
   100 loops, best of 3: 11.5 ms per loop
   

   Cython 구현 (이 프로젝트에서는 사용할 수 없음)을 시도하지 않았지만 결과를 다른 답변과 비교하면 scipy.spatial.distance.pdist는 Cython 구현보다 약 3 분의 1 느린 것 같습니다. (np.abs 솔루션의 벤치마킹을 통해 여러 시스템을 고려해야 함).

2. ==============================

   2.다음은 내 컴퓨터에서이 예제에 대해 3 배 이상의 속도 향상을 제공하는 Cython 구현입니다. BLAS 루틴이 다소 단순한 코드보다 훨씬 더 확장 될 수 있기 때문에 더 큰 배열에 대해서는이 타이밍을 검토해야합니다.

   다음은 내 컴퓨터에서이 예제에 대해 3 배 이상의 속도 향상을 제공하는 Cython 구현입니다. BLAS 루틴이 다소 단순한 코드보다 훨씬 더 확장 될 수 있기 때문에 더 큰 배열에 대해서는이 타이밍을 검토해야합니다.

   나는 당신이 scipy / numpy / scikit-learn 안에 뭔가를 요청했다는 것을 압니다, 그러나 아마도 이것은 당신에게 새로운 가능성을 열어 줄 것입니다 :

   my_cython.pyx 파일 :

   import numpy as np
   cimport numpy as np
   import cython
   
   cdef extern from "math.h":
       double abs(double t)
   
   @cython.wraparound(False)
   @cython.boundscheck(False)
   def pairwise_distance(np.ndarray[np.double_t, ndim=1] r):
       cdef int i, j, c, size
       cdef np.ndarray[np.double_t, ndim=1] ans
       size = sum(range(1, r.shape[0]+1))
       ans = np.empty(size, dtype=r.dtype)
       c = -1
       for i in range(r.shape[0]):
           for j in range(i, r.shape[0]):
               c += 1
               ans[c] = abs(r[i] - r[j])
       return ans
   

   대답은 모든 반복되지 않는 평가를 포함하는 일차원 배열입니다.

   파이썬으로 임포트하려면,

   import numpy as np
   import random
   
   import pyximport; pyximport.install()
   from my_cython import pairwise_distance
   
   r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)], dtype=float)
   
   def solOP(r):
       return np.abs(r - r[:, None])
   

   IPython으로 타이밍하기 :

   In [2]: timeit solOP(r)
   100 loops, best of 3: 7.38 ms per loop
   
   In [3]: timeit pairwise_distance(r)
   1000 loops, best of 3: 1.77 ms per loop
   

3. ==============================

   3.절반의 메모리를 사용하지만 np.abs (r - r [:, None])보다 6 배 느립니다.

   절반의 메모리를 사용하지만 np.abs (r - r [:, None])보다 6 배 느립니다.

   triu = np.triu_indices(r.shape[0],1)
   dists2 = abs(r[triu[1]]-r[triu[0]])
   

from https://stackoverflow.com/questions/20277982/fastest-pairwise-distance-metric-in-python by cc-by-sa and MIT license