我编写了一些包含嵌套循环的代码,其中内循环执行了大约 150 万次。我正在尝试优化此循环中的一个函数。我已经完成了一些工作并获得了一些结果,但我需要一些输入来检查我正在做的事情是否明智。
一些背景:
我有两个地理点集合(纬度、经度),一个相对较小的集合和一个相对较大的集合。对于小集合中的每个点,我需要在大集合中找到最近的点。
执行此操作的明显方法是使用半正弦公式。这样做的好处是距离绝对准确。
from math import radians, sin, cos, asin, sqrt
def haversine(point1, point2):
"""Gives the distance between two points on earth.
"""
earth_radius_miles = 3956
lat1, lon1 = (radians(coord) for coord in point1)
lat2, lon2 = (radians(coord) for coord in point2)
dlat, dlon = (lat2 - lat1, lon2 - lon1)
a = sin(dlat/2.0)**2 + cos(lat1) * cos(lat2) * sin(dlon/2.0)**2
great_circle_distance = 2 * asin(min(1,sqrt(a)))
d = earth_radius_miles * great_circle_distance
return d
但是,在我的机器上运行这 150 万次大约需要 9 秒(根据 timeit)。由于准确的距离并不重要,我只需要找到最近的点,我决定尝试一些其他功能。
毕达哥拉斯定理的简单实现使我的速度提高了大约 30%。认为我可以做得更好,我写了以下内容:
def dumb(point1, point2):
lat1, lon1 = point1
lat2, lon2 = point2
d = abs((lat2 - lat1) + (lon2 - lon1))
这给了我 10 倍的改进。但是,现在我担心这不会保留三角不等式。
所以,我的最后一个问题有两个:我想要一个运行速度与dumb
一样快但仍然正确的函数。 dumb
会工作吗?如果没有,关于如何改进我的 haversine 函数的任何建议?
最佳答案
这就是 numpy 的那种计算真的很擅长。您可以在一次计算中计算单个点与整个数据集之间的距离,而不是遍历整个大型坐标集。通过下面的测试,您可以获得一个数量级的速度提升。
这是使用您的 haversine
方法、您的 dumb
方法(不太确定它做了什么)和我的 numpy haversine 方法进行的一些计时测试。它计算两点之间的距离 - 一个在弗吉尼亚州,一个在加利福尼亚州,相距 2293 英里。
from math import radians, sin, cos, asin, sqrt, pi, atan2
import numpy as np
import itertools
earth_radius_miles = 3956.0
def haversine(point1, point2):
"""Gives the distance between two points on earth.
"""
lat1, lon1 = (radians(coord) for coord in point1)
lat2, lon2 = (radians(coord) for coord in point2)
dlat, dlon = (lat2 - lat1, lon2 - lon1)
a = sin(dlat/2.0)**2 + cos(lat1) * cos(lat2) * sin(dlon/2.0)**2
great_circle_distance = 2 * asin(min(1,sqrt(a)))
d = earth_radius_miles * great_circle_distance
return d
def dumb(point1, point2):
lat1, lon1 = point1
lat2, lon2 = point2
d = abs((lat2 - lat1) + (lon2 - lon1))
return d
def get_shortest_in(needle, haystack):
"""needle is a single (lat,long) tuple.
haystack is a numpy array to find the point in
that has the shortest distance to needle
"""
dlat = np.radians(haystack[:,0]) - radians(needle[0])
dlon = np.radians(haystack[:,1]) - radians(needle[1])
a = np.square(np.sin(dlat/2.0)) + cos(radians(needle[0])) * np.cos(np.radians(haystack[:,0])) * np.square(np.sin(dlon/2.0))
great_circle_distance = 2 * np.arcsin(np.minimum(np.sqrt(a), np.repeat(1, len(a))))
d = earth_radius_miles * great_circle_distance
return np.min(d)
x = (37.160316546736745, -78.75)
y = (39.095962936305476, -121.2890625)
def dohaversine():
for i in xrange(100000):
haversine(x,y)
def dodumb():
for i in xrange(100000):
dumb(x,y)
lots = np.array(list(itertools.repeat(y, 100000)))
def donumpy():
get_shortest_in(x, lots)
from timeit import Timer
print 'haversine distance =', haversine(x,y), 'time =',
print Timer("dohaversine()", "from __main__ import dohaversine").timeit(100)
print 'dumb distance =', dumb(x,y), 'time =',
print Timer("dodumb()", "from __main__ import dodumb").timeit(100)
print 'numpy distance =', get_shortest_in(x, lots), 'time =',
print Timer("donumpy()", "from __main__ import donumpy").timeit(100)
这是它打印的内容:
haversine distance = 2293.13242188 time = 44.2363960743
dumb distance = 40.6034161104 time = 5.58199882507
numpy distance = 2293.13242188 time = 1.54996609688
numpy 方法需要 1.55 秒来计算相同数量的距离计算,因为它需要 44.24 秒来计算你的函数方法。通过将一些 numpy 函数组合到一个语句中,您可能会获得更多的加速,但它会变得很长,难以阅读。
关于Python:加速地理比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6656475/