Der schnellste Weg mit der Parallelisierung, um Abstände zwischen zwei Punkten mit Python-Code

Question

zu berechnen Ich habe einen Datenrahmen 'Daten' mit Millionen von Zeilen. Jede Zeile hat Koordinaten ('x', 'y'), ich möchte Abstände zwischen aufeinanderfolgenden Koordinatenpaaren auf die effizienteste Weise berechnen, die Python liefern kann. Wird die Parallelisierung hier helfen?

Ich sah Ansätze hier, die Cython verwenden vorgeschlagen. Allerdings möchte ich nur Python-Lösungen sehen. Hier

ist das Snippet meiner Daten

points = 
[(26406, -6869), 
(27679, -221), 
(27679, -221), 
(26416, -6156), 
(26679, -578), 
(26679, -580), 
(27813, -558), 
(26254, -1097), 
(26679, -580), 
(27813, -558), 
(28258, -893), 
(26253, -1098), 
(26678, -581), 
(27811, -558), 
(28259, -893), 
(26252, -1098), 
(27230, -481), 
(26679, -582), 
(27488, -5849), 
(27811, -558), 
(28259, -893), 
(26250, -1099), 
(27228, -481), 
(26679, -582), 
(27488, -5847), 
(28525, -1465), 
(27811, -558), 
(28259, -892)] 

Ich glaube, dass mein erster Ansatz für-Schleife kann auf jeden Fall verbessert werden:

from scipy.spatial import distance 
    def comp_dist(points): 
     size =len(points) 
     d = 0 
     i=1 
     for i in range(1,size): 
      if i%1000000==0: 
       print i 
      # print "i-1:", points[i-1] 
      # print "i: ", points[i] 
      dist = distance.euclidean(points[i-1],points[i]) 
      d= d+dist 
     print d 

    distance = comp_dist(points) 

Vielen Dank für Ihre Antworten im Voraus.

Answer 1

Hier ist ein kurzes Beispiel, um Ihnen den Einstieg:

from scipy.spatial import distance 
from multiprocessing import Pool 

processes = 4 

# Group data into pairs in order to compute distance 
pairs = [(points[i], points[i+1]) for i in range(len(points)-1)] 
print pairs 

# Split data into chunks 
l = [pairs[i:i+processes] for i in xrange(0, len(pairs), processes)] 


def worker(lst): 
    return [distance.euclidean(i[0], i[1]) for i in lst] 

if __name__ == "__main__": 
    p = Pool(processes) 
    result = p.map(worker, l) 
    # Flatten list 
    print [item for sublist in result for item in sublist] 

Testing dies mit:

points =[(random.randint(0,1000), random.randint(0, 1000)) for i in range(1000000)] 

Mit 8 verarbeitet es etwa 5 Sekunden dauert, mit 1 mehr als 10 Sekunden dauert.

Answer 2

Sie sagten Python, aber da Sie bereits scipy für die Entfernungsberechnung verwenden, nehme ich an, dass eine numpige Lösung in Ordnung ist.

Die Verwendung einer vektorisierten, single-threaded Operation auf einem 28 Millionen Punkte numpy Array dauert nur 1 Sekunde auf meinem Laptop. Mit einem 32-Bit-Integer-Datentyp belegt das Array etwa 200 MB im Speicher.

import numpy as np 
points = [(26406, -6869), ..., (28259, -892)] 
# make test array my repeating the 28-element points list 1M times 
np_points = np.array(points*1000000, dtype='int32') 
# use two different slices (offset by 1) from resulting array; 
# execution of next line takes ~1 second 
dists = np.sqrt(np.sum((np_points[0:-2] - np_points[1:-1])**2, axis=1)) 

print(dists.shape) 
(27999998,) 

print(dists[:28]) 
[ 6.76878372e+03 0.00000000e+00 6.06789865e+03 5.58419672e+03 
    2.00000000e+00 1.13421338e+03 1.64954600e+03 6.69263775e+02 
    1.13421338e+03 5.57000898e+02 2.01545280e+03 6.69263775e+02 
    1.13323343e+03 5.59400572e+02 2.01744244e+03 1.15636197e+03 
    5.60180328e+02 5.32876815e+03 5.30084993e+03 5.59400572e+02 
    2.01953386e+03 1.15689585e+03 5.58213221e+02 5.32679134e+03 
    4.50303153e+03 1.15431581e+03 5.58802291e+02 6.25764636e+03]