La métrica de distancia por pares más rápida en python

Tengo un conjunto de números 1D y quiero calcular todas las distancias euclidianas por pares. Tengo un método (gracias a SO) para hacer esto con la transmisión, pero es ineficiente porque calcula cada distancia dos veces. Y no se escala bien.

Aquí hay un ejemplo que me da lo que quiero con una matriz de 1000 números.

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

¿Cuál es la implementación más rápida en scipy / numpy / scikit-learn que puedo usar para hacer esto, dado que tiene que escalar a situaciones donde la matriz 1D tiene valores> 10k?

Nota: la matriz es simétrica, por lo que supongo que es posible obtener una aceleración de al menos 2 veces abordando eso, pero no sé cómo.

Ninguna de las otras respuestas contestó la pregunta: 1 estaba en Cython, una era más lenta. Pero ambos proporcionaron consejos muy útiles. El seguimiento de ellos sugiere que scipy.spatial.distance.pdist es el camino a seguir.

Aquí hay un código:

 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) 

Tiempo con 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 

No probé la implementación de Cython (no puedo usarla para este proyecto), pero al comparar mis resultados con la otra respuesta, parece que scipy.spatial.distance.pdist es aproximadamente un tercio más lento que la implementación de Cython (Teniendo en cuenta las diferentes máquinas mediante la evaluación comparativa en la solución np.abs).

Aquí hay una implementación de Cython que proporciona una mejora de la velocidad de más de 3X para este ejemplo en mi computadora. Este tiempo debe ser revisado para arreglos más grandes, porque las rutinas BLAS probablemente pueden escalar mucho mejor que este código bastante ingenuo.

Sé que pediste algo dentro de scipy / numpy / scikit-learn, pero quizás esto te abrirá nuevas posibilidades:

Archivo 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 

La respuesta es una matriz 1-D que contiene todas las evaluaciones no repetidas.

Para importar en Python:

 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]) 

Tiempo con 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 

Usando la mitad de la memoria, pero 6 veces más lento que np.abs(r - r[:, None]) :

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