Haversine距离最小计算的高效求解

2024-03-29 08:35:58 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个2.7MM坐标的数据帧,还有一个2000个坐标的单独列表。我试图返回每一行中的坐标与列表中每个坐标之间的最小距离。下面的代码在小范围内工作(dataframe有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)

我知道问题在于正在进行的计算的数量之多(57mm*2000=~114亿),而且运行这么多循环的效率非常低。在

根据我的研究,向量化的NumPy函数似乎是一个更好的方法,但是我对Python和NumPy还不太熟悉,所以我不太确定在这种特殊情况下如何实现它。在

理想输出:

^{pr2}$

提前谢谢!在


Tags: indf列表forcoordsminlistend
1条回答
网友
1楼 · 发布于 2024-03-29 08:35:58

^{}的本质是:

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

这里有一个向量化方法,利用强大的^{}NumPy ufuncs来替换这些数学模块函数,这样我们就可以一次性地对整个数组进行操作-

^{pr2}$

为了进一步提高性能,我们可以使用^{} 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

相关问题 更多 >