Pythonコードで2つのポイント間の距離を計算するための並列化の最速方法

Question

私は何百万という行のデータフレーム 'data'を持っています。各行には座標（ 'x'、 'y'）があり、Pythonが提供する最も効率的な方法で連続した座標のペア間の距離を計算したいと思います。並列化はここで助けますか？

ここでは、cythonを使用することを示唆しています。しかし、私はPythonのソリューションだけを見たいと思います。ここで

は、私がforループ使用して私の最初のアプローチは確実に向上させることができると信じている私のデータのスニペット

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

です：

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) 

は、事前にあなたの答えをありがとうございました。ここで

Answer 1

はあなたが始めるのに役立つ簡単な例です：

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] 

テストこれで：

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

8つのプロセスで、それは10秒を引き継ぎ1で、約5秒かかります。

Answer 2

あなたはPythonを使っていますが、すでに距離計算にscipyを使用しているので、私はnumpyの解決策はOKだと思います。

私のラップトップでは、2800万ポイントのnumpy配列でベクトル化されたシングルスレッド操作を使用するとわずか1秒しかかかりません。 32ビットの整数データ型を使用すると、配列は約200MBのメモリを占有します。あなたの現在のソリューションよりも速く、そしてCythonよりも実装がずっと簡単だろうnumpyのを使用して

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]