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.Schnellste Weg, Abstand zwischen jedem Punkte in Python zu berechnen
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.
Wenn Sie die Entfernungen nicht benötigen und nur auf die Unterschiede/Rangfolge achten, können Sie die sqrt-Datei loswerden. Dies sollte der langsamste Teil Ihrer Berechnung sein. Vielleicht könnten Sie auch eine schnellere sqrt verwenden, die nicht so präzise ist oder eine andere Metrik verwenden (z. B. Taxi). – sascha
Mit 5000 bis 6000 Punkten hat Ihre Matrix etwa 30 Millionen Einträge. Das Berechnen einer Quadratwurzel 30 m mal ist zwangsläufig langsam. Brauchen Sie wirklich die volle, dichte Matrix? Was machst du nach der Berechnung mit der Matrix? –
Wie viel schneller ist numpy als Cython? – sebacastroh