Python：加快地理比较

Question

我已经写了一些代码，包括其中内环路约1.5万次执行的嵌套循环。我在这个循环的功能，我试图以优化。我已经做了一些工作，并取得了一些成果，但我需要查了一下输入，如果我在做什么是明智的。

一些背景：

我有两个地理点（纬度，经度）集合，一个相对较小的集合，一个相对较大的集合。对于小集合的每一个点，我需要找到大集合中的最近点。

最明显的方式做到这一点是使用haversine公式。这里的好处是，距离是绝对准确的。

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万次（根据timeit）把我的机器上约9秒。由于具有精确的距离是不重要的，而我只需要找到的最近点，我决定尝试一些其他的功能。

一个简单的实现勾股定理给我的约30％的速度提升。以为我可以做的更好，我写了下面：

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

这给了我10改进的一个因素。不过，现在我担心，这将不保留三角不等式。

所以，我的最后一个问题是双重的：我想有一个功能，运行快，dumb但仍然是正确的。会dumb工作吗？如果没有，就如何提高我的半正矢函数有什么建议？

Answer 1

您可以考虑某种图形哈希，即快速找到最接近的点，然后对其进行计算。例如，你可以创建一个统一的网格，并分发（的大集合）的点是由网格创建的垃圾箱。

现在，具有与小集合点，你需要处理点小得多量（即是在相关箱只）