Я написал код, который включает вложенный цикл, где внутренний цикл выполняется примерно 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
Однако запуск этого 1,5 миллиона раз занимает около 9 секунд на моей машине (в соответствии с timeit). Поскольку точное расстояние не имеет значения, скорее мне нужно всего лишь найти ближайшую точку, я решил попробовать другие функции.
Простая реализация теоремы о пифагоре дает мне скорость около 30%. Думая, что я могу сделать лучше, я написал следующее:
def dumb(point1, point2):
lat1, lon1 = point1
lat2, lon2 = point2
d = abs((lat2 - lat1) + (lon2 - lon1))
что дает мне улучшение в 10 раз. Однако теперь я беспокоюсь, что это не сохранит неравенство треугольника.
Итак, мой последний вопрос в два раза: я хотел бы иметь функцию, которая работает так же быстро, как dumb, но все равно будет правильной. Будет ли работать dumb? Если нет, какие-либо предложения о том, как улучшить мою функцию haversine?
