Python:加快地理比较

Question

我编写了一些包含嵌套循环的代码,其中内循环执行大约150万次.我在这个循环中有一个函数,我正在尝试优化.我做了一些工作,并得到了一些结果,但我需要一些输入来检查我所做的事情是否合情合理.

一些背景:

我有两个地理点集合(纬度,经度),一个相对较小的集合和一个相对庞大的集合.对于小集合中的每个点,我需要找到大集合中的最近点.

显而易见的方法是使用hasrsine公式.这里的好处是距离绝对准确.

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秒(根据时间).由于准确的距离并不重要,我只需要找到最近的点,我决定尝试其他一些功能.

毕达哥拉斯定理的简单实现给了我大约30%的加速.考虑到我可以做得更好,我写了以下内容:

def dumb(point1, point2):
    lat1, lon1 = point1
    lat2, lon2 = point2
    d = abs((lat2 - lat1) + (lon2 - lon1))

这让我有10倍的改进.但是,现在我担心这不会保留三角不等式.

所以,我的最后一个问题是两个方面:我想要一个运行速度尽可能快dumb但仍然正确的函数.会dumb工作吗？如果没有,有关如何改善我的半身功能的任何建议？

Answer 1

这是numpy真正擅长的计算方式.您可以在单个计算中计算单个点与整个数据集之间的距离,而不是遍历整个大型坐标集.通过下面的测试,您可以获得一个数量级的速度提升.

这里有一些时间测试,你的haversine方法,你的dumb方法(不确定是什么)和我的numpy hasrsine方法.它计算两点之间的距离 - 一个在弗吉尼亚州,另一个在加利福尼亚州,距离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函数组合到一个语句中,你可能会获得更多的加速,但它将成为一个冗长,难以阅读的行.

Answer 2

您可以考虑某种图形哈希,即快速找到最近点,然后计算它们.例如,您可以创建一个统一的网格,并将(大集合的)点分配到网格创建的箱中.

现在,从小集合中得到一个点,你需要处理更少量的点(即仅在相关的箱中)