Schnellste Weg, Abstand zwischen jedem Punkte in Python zu berechnen

Question

In meinem Projekt muss ich Euklidian Abstand zwischen jedem Punkt in einem Array gespeichert berechnen. Das Entry-Array ist ein 2D-Numpy-Array mit 3 Spalten, die die Koordinaten (x, y, z) bilden und jede Reihe einen neuen Punkt definiert.

Ich arbeite normalerweise mit 5000 - 6000 Punkten in meinen Testfällen.

Mein erster Algorithmus verwenden Cython und meine zweite numpy. Ich finde, dass mein numpy Algorithmus schneller ist als Cython.

edit: mit 6000 Punkten:

numpy 1,76 s/cython 4,36 s

Hier ist mein cython Code:

cimport cython 
from libc.math cimport sqrt 
@cython.boundscheck(False) 
@cython.wraparound(False) 
cdef void calcul1(double[::1] M,double[::1] R): 

    cdef int i=0 
    cdef int max = M.shape[0] 
    cdef int x,y 
    cdef int start = 1 

    for x in range(0,max,3): 
    for y in range(start,max,3): 

     R[i]= sqrt((M[y] - M[x])**2 + (M[y+1] - M[x+1])**2 + (M[y+2] - M[x+2])**2) 
     i+=1 

    start += 1 

M ist eine Speicheransicht des Ersteinreise Array aber flatten() durch vor dem Aufruf der Funktion calcul1() ist R eine Speicheransicht eines 1D-Ausgangsarrays zum Speichern aller Ergebnisse.

Hier ist mein Numpy Code:

def calcul2(M): 

    return np.sqrt(((M[:,:,np.newaxis] - M[:,np.newaxis,:])**2).sum(axis=0)) 

Hier M die anfängliche Eintraganordnung ist, aber durch transpose() numpy bevor der Aufruf der Funktion Koordinaten haben (x, y, z) als Zeilen und Punkte wie Spalten.

Außerdem ist diese numpy Funktion ziemlich convinient, weil das Array, das es zurückbringt, gut organisiert ist. Es ist ein Array n n mit n die Anzahl der Punkte und jeder Punkt hat eine Zeile und eine Spalte. So zum Beispiel der Abstand AB an der Kreuzung Index der Reihe A und Spalte B gespeichert

Hier ist, wie ich sie nenne (cython-Funktion):

cpdef test(): 

    cdef double[::1] Mf 
    cdef double[::1] out = np.empty(17998000,dtype=np.float64) # (6000² - 6000)/2 

    M = np.arange(6000*3,dtype=np.float64).reshape(6000,3) # Example array with 6000 points 
    Mf = M.flatten() #because my cython algorithm need a 1D array 
    Mt = M.transpose() # because my numpy algorithm need coordinates as rows 

    calcul2(Mt) 

    calcul1(Mf,out) 

ich etwas falsch hier tue? Für mein Projekt sind beide nicht schnell genug.

1: Gibt es eine Möglichkeit, meinen Cython-Code zu verbessern, um die Geschwindigkeit von numpy zu übertreffen?

2: Gibt es eine Möglichkeit, meinen Code zu verbessern, um noch schneller zu berechnen?

3: Oder andere Lösungen, aber es muss ein Python/Cython (wie Parallel Computing) sein?

Vielen Dank.

Answer 1

nicht sicher, wo Sie Ihre Timings bekommen, aber Sie können verwenden scipy.spatial.distance:

M = np.arange(6000*3, dtype=np.float64).reshape(6000,3) 
np_result = calcul2(M) 
sp_result = sd.cdist(M.T, M.T) #Scipy usage 
np.allclose(np_result, sp_result) 
>>> True 

Timings:

%timeit calcul2(M) 
1000 loops, best of 3: 313 µs per loop 

%timeit sd.cdist(M.T, M.T) 
10000 loops, best of 3: 86.4 µs per loop 

Wichtig ist, es ist auch nützlich, zu erkennen, dass die Ausgabe symmetrisch ist:

np.allclose(sp_result, sp_result.T) 
>>> True 

Eine Alternative besteht darin, nur das obere Dreieck dieses Arrays zu berechnen:

Edit: Nicht sicher, welchen Index Sie zippen möchten, sieht aus wie Sie es in beide Richtungen tun können? Zippen des anderen Index zum Vergleich:

%timeit sd.pdist(M) 
10 loops, best of 3: 135 ms per loop 

Noch etwa 10x schneller als Ihre aktuelle NumPy-Implementierung.