Python:加速地理比较
我写了一些代码，其中包含一个嵌套循环，其中内部循环被执行了大约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会工作吗？如果没有，有什么建议可以改进我的半正弦函数吗？
回答 6
Stack Overflow用户
发布于 2011-07-12 05:01:34
您可以考虑某种图形散列，即快速找到最接近的点，然后在它们上进行计算。例如，您可以创建一个统一的栅格，并将(大型集合的)点分布在栅格创建的存储箱中。
现在，有了一个来自小集合的点，你需要处理的点数要少得多(即，仅处理相关存储箱中的点)。
Stack Overflow用户
发布于 2011-07-12 13:24:53
这是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.54996609688numpy方法计算距离计算所需的时间为1.55秒，与使用函数方法计算44.24秒的计算次数相同。通过将一些numpy函数组合到一条语句中，您可能会获得更大的加速，但这将成为一个很长的、难以阅读的行。
Stack Overflow用户
发布于 2011-07-12 05:28:28
你写的公式(d=abs(lat2-lat1)+(lon2-lon1))不能保持三角形不等式:如果你找到lat，lon，其中d是最小的，你找不到最近的点，但最接近于两条对角线在你正在检查的点相交的点！
我认为你应该按经度和经度对大量的点进行排序(这意味着：(1,1)，(1,2)，(1,3)...(2,1)，(2,2)等。然后使用gunner方法找到一些在纬度和经度方面最接近的点(这应该是非常快的，它将占用与ln2 (n)成比例的cpu时间，其中n是点数)。你可以很容易地做到这一点，举个例子:在你要检查的点周围选择10x10的平方中的所有点，这意味着:在lat (枪手方法)中找到所有从-10到+10的点，然后再找到那些在lon (枪手方法)中从-10到+10的点。现在你有一个非常小的数据量去处理，它应该是非常快的！
https://stackoverflow.com/questions/6656475
复制相似问题
腾讯云开发者
