効率的な計算は

Question

私は> 2.7mmの座標とデータフレーム、および 2,000〜のは座標別々リストを持っている距離。私はのとの座標の間の最小距離をのリストと比較して返すようにしています。以下のコードは小規模（200行のデータフレーム）で動作しますが、2.7MM以上の行を計算すると、一見無限に実行されます。

from haversine import haversine 

df 
Latitude Longitude 
39.989 -89.980 
39.923 -89.901 
39.990 -89.987 
39.884 -89.943 
39.030 -89.931 

end_coords_list = [(41.342,-90.423),(40.349,-91.394),(38.928,-89.323)] 

for row in df.itertuples(): 
    def min_distance(row): 
     beg_coord = (row.Latitude, row.Longitude) 
     return min(haversine(beg_coord, end_coord) for end_coord in end_coords_list) 
    df['Min_Distance'] = df.apply(min_distance, axis=1) 

私は、問題が起こっている計算の膨大な数（5.7MM * 2000 =〜11.4BN）、そしてこの多数のループを実行すると、信じられないほど非効率的であるという事実にある知っています。

私の研究に基づいて、ベクトル化されたNumPy関数がより良いアプローチかもしれないと思われますが、私はPythonとNumPyを初めて使用しているので、この特定の状況でこれを実装する方法はあまりよく分かりません。

理想的な出力：事前に

df 
Latitude Longitude Min_Distance 
39.989 -89.980  3.7 
39.923 -89.901  4.1 
39.990 -89.987  4.2 
39.884 -89.943  5.9 
39.030 -89.931  3.1 

ありがとう！

Answer 1

本質的にhaversine funcは次のとおりです。

# convert all latitudes/longitudes from decimal degrees to radians 
lat1, lng1, lat2, lng2 = map(radians, (lat1, lng1, lat2, lng2)) 

# calculate haversine 
lat = lat2 - lat1 
lng = lng2 - lng1 

d = sin(lat * 0.5) ** 2 + cos(lat1) * cos(lat2) * sin(lng * 0.5) ** 2 
h = 2 * AVG_EARTH_RADIUS * asin(sqrt(d)) 

ここでは、一度に全体の配列上で動作するように、それらの数学モジュールのfuncsを置き換えるために、強力なNumPy broadcastingとNumPy ufuncsを活用ベクトル化の方法だ -

# Get array data; convert to radians to simulate 'map(radians,...)' part  
coords_arr = np.deg2rad(coords_list) 
a = np.deg2rad(df.values) 

# Get the differentiations 
lat = coords_arr[:,0] - a[:,0,None] 
lng = coords_arr[:,1] - a[:,1,None] 

# Compute the "cos(lat1) * cos(lat2) * sin(lng * 0.5) ** 2" part. 
# Add into "sin(lat * 0.5) ** 2" part. 
add0 = np.cos(a[:,0,None])*np.cos(coords_arr[:,0])* np.sin(lng * 0.5) ** 2 
d = np.sin(lat * 0.5) ** 2 + add0 

# Get h and assign into dataframe 
h = 2 * AVG_EARTH_RADIUS * np.arcsin(np.sqrt(d)) 
df['Min_Distance'] = h.min(1) 

パフォーマンスをさらに向上させるために、超越機能を置き換えるためにnumexpr moduleを使用できます。

---

ランタイムテストおよび検証

アプローチ -

def loopy_app(df, coords_list): 
    for row in df.itertuples(): 
     df['Min_Distance1'] = df.apply(min_distance, axis=1) 

def vectorized_app(df, coords_list): 
    coords_arr = np.deg2rad(coords_list) 
    a = np.deg2rad(df.values) 

    lat = coords_arr[:,0] - a[:,0,None] 
    lng = coords_arr[:,1] - a[:,1,None] 

    add0 = np.cos(a[:,0,None])*np.cos(coords_arr[:,0])* np.sin(lng * 0.5) ** 2 
    d = np.sin(lat * 0.5) ** 2 + add0 

    h = 2 * AVG_EARTH_RADIUS * np.arcsin(np.sqrt(d)) 
    df['Min_Distance2'] = h.min(1) 

検証 -

In [158]: df 
Out[158]: 
    Latitude Longitude 
0 39.989 -89.980 
1 39.923 -89.901 
2 39.990 -89.987 
3 39.884 -89.943 
4 39.030 -89.931 

In [159]: loopy_app(df, coords_list) 

In [160]: vectorized_app(df, coords_list) 

In [161]: df 
Out[161]: 
    Latitude Longitude Min_Distance1 Min_Distance2 
0 39.989 -89.980  126.637607  126.637607 
1 39.923 -89.901  121.266241  121.266241 
2 39.990 -89.987  126.037388  126.037388 
3 39.884 -89.943  118.901195  118.901195 
4 39.030 -89.931  53.765506  53.765506 

タイミング -

In [163]: df 
Out[163]: 
    Latitude Longitude 
0 39.989 -89.980 
1 39.923 -89.901 
2 39.990 -89.987 
3 39.884 -89.943 
4 39.030 -89.931 

In [164]: %timeit loopy_app(df, coords_list) 
100 loops, best of 3: 2.41 ms per loop 

In [165]: %timeit vectorized_app(df, coords_list) 
10000 loops, best of 3: 96.8 µs per loop