Каждая строка таблицы данных содержит панды широта/СПГ координаты 2-х точек. С помощью кода на Python ниже, вычисления расстояния между 2 точками для многих (миллионы) строк занимает очень много времени!
Учитывая, что 2 очка в 50 миль, и точность не очень важна, можно ли сделать расчет быстрее?
from math import radians, cos, sin, asin, sqrt
def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
km = 6367 * c
return km
for index, row in df.iterrows():
df.loc[index, 'distance'] = haversine(row['a_longitude'], row['a_latitude'], row['b_longitude'], row['b_latitude'])
Вот версия включает в себя векторные функции:
import numpy as np
def haversine_np(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
All args must be of equal length.
"""
lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
dlon = lon2 - lon1
dlat = lat2 - lat1
a = np.sin(dlat/2.0)**2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2.0)**2
c = 2 * np.arcsin(np.sqrt(a))
km = 6367 * c
return km
Входы всех наборов значений, и он должен уметь делать миллионы точек мгновенно. Требование заключается в том, что входы ndarrays а столбцы таблицы панды будет работать.
Например, с случайно сгенерированных значений:
>>> import numpy as np
>>> import pandas
>>> lon1, lon2, lat1, lat2 = np.random.randn(4, 1000000)
>>> df = pandas.DataFrame(data={'lon1':lon1,'lon2':lon2,'lat1':lat1,'lat2':lat2})
>>> km = haversine_np(df['lon1'],df['lat1'],df['lon2'],df['lat2'])
Или если вы хотите создать еще один столбец:
>>> df['distance'] = haversine_np(df['lon1'],df['lat1'],df['lon2'],df['lat2'])
Циклы по массивам данных происходит очень медленно в Python. Numpy содержит функции, которые работают на всю массивы данных, что позволяет избежать зацикливания и значительно повысить производительность.
Это пример векторизация.
Чисто ради примера, я взял и NumPy версия в ответ от @ballsdotballs и товарищ Си через под
. Так включает в себя
такой оптимизированный инструмент, есть небольшой шанс, что мой код на C будет работать так эффективно, но оно должно быть достаточно близко. Большим преимуществом здесь является то, что, запустив пример с типами, он может помочь вам увидеть, как вы можете подключить свой личный C функции в Python без особых накладных расходов. Это особенно приятно, когда вы просто хотите оптимизировать небольшой кусок побольше вычислений, написав, что небольшой кусок в некоторых с источника, а не питона. Просто с помощью включает в себя
решит проблему, но для тех случаев, когда вы не't действительно нужно все библиотеки numpy и вы Don'т хотите, чтобы добавить соединение требует использования включает в себя
типы данных в течение некоторого кода, это'ы очень полезно знать, как опуститься в встроенной под библиотеку и сделать это самостоятельно.
Сначала позвольте's создавать наши c исходный файл, называемый гаверсинус.с
:
в
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int haversine(size_t n,
double *lon1,
double *lat1,
double *lon2,
double *lat2,
double *kms){
if ( lon1 == NULL
|| lon2 == NULL
|| lat1 == NULL
|| lat2 == NULL
|| kms == NULL){
return -1;
}
double km, dlon, dlat;
double iter_lon1, iter_lon2, iter_lat1, iter_lat2;
double km_conversion = 2.0 * 6367.0;
double degrees2radians = 3.14159/180.0;
int i;
for(i=0; i < n; i++){
iter_lon1 = lon1[i] * degrees2radians;
iter_lat1 = lat1[i] * degrees2radians;
iter_lon2 = lon2[i] * degrees2radians;
iter_lat2 = lat2[i] * degrees2radians;
dlon = iter_lon2 - iter_lon1;
dlat = iter_lat2 - iter_lat1;
km = pow(sin(dlat/2.0), 2.0)
+ cos(iter_lat1) * cos(iter_lat2) * pow(sin(dlon/2.0), 2.0);
kms[i] = km_conversion * asin(sqrt(km));
}
return 0;
}
// main function for testing
int main(void) {
double lat1[2] = {16.8, 27.4};
double lon1[2] = {8.44, 1.23};
double lat2[2] = {33.5, 20.07};
double lon2[2] = {14.88, 3.05};
double kms[2] = {0.0, 0.0};
size_t arr_size = 2;
int res;
res = haversine(arr_size, lon1, lat1, lon2, lat2, kms);
printf("%d\n", res);
int i;
for (i=0; i < arr_size; i++){
printf("%3.3f, ", kms[i]);
}
printf("\n");
}
Обратите внимание, что мы'вновь пытается сохранить с конвенций с. Явно передавая данные доводы со ссылкой, используя реализация
для переменной размер, и ожидая наш гаверсинус
функции для работы с мутирующими один из переданных входами, так что он будет содержать ожидаемые данные на выходе. Функция на самом деле возвращает целое число, которое является успех/флаг неудач, которые могут быть использованы другими c-уровня потребителей функции.
Мы'вновь придется найти способ, чтобы обработать все эти маленькие с конкретных вопросов внутри питона.
Далее, позвольте'ы поставили нашей библиотеки numpy версия функция вместе с некоторым импортом и некоторые тестовые данные в файл haversine.py
:
import time
import ctypes
import numpy as np
from math import radians, cos, sin, asin, sqrt
def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = (np.sin(dlat/2)**2
+ np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2)**2)
c = 2 * np.arcsin(np.sqrt(a))
km = 6367 * c
return km
if __name__ == "__main__":
lat1 = 50.0 * np.random.rand(1000000)
lon1 = 50.0 * np.random.rand(1000000)
lat2 = 50.0 * np.random.rand(1000000)
lon2 = 50.0 * np.random.rand(1000000)
t0 = time.time()
r1 = haversine(lon1, lat1, lon2, lat2)
t1 = time.time()
print t1-t0, r1
Я решил сделать лат и Лон (в градусах), которые выбираются случайным образом между 0 и 50, но это вовсе'т имеет значения слишком много для такого объяснения.
Следующее, что нам нужно сделать, это скомпилировать модуль c таким образом, что она может быть динамически загружен в Python. Я'м через системы Linux (вы можете найти примеры для других систем очень легко в Гугле), поэтому моей задачей является компиляция гаверсинус.С
в разделяемый объект, вот так:
gcc -shared -o haversine.so -fPIC haversine.c -lm
Мы также можем скомпилировать в исполняемый файл и запустить его, чтобы увидеть, какие программы c's в функции main
отображает:
> gcc haversine.c -o haversine -lm
> ./haversine
0
1964.322, 835.278,
Теперь, когда мы собрали гаверсинус общий объект.таким образом, мы можем использовать
под`, чтобы загрузить его в Python и нам нужно указать путь к файлу для этого:
lib_path = "/path/to/haversine.so" # Obviously use your real path here.
haversine_lib = ctypes.CDLL(lib_path)
Теперь haversine_lib.акты гаверсинус довольно много, почти как функция Python, за исключением того, что мы, возможно, должны сделать некоторые ручного типа маршалинга, чтобы убедиться, что входы и выходы будут интерпретироваться правильно.
включает в себя
действительно обеспечивает некоторые хорошие инструменты для этого, и я'будете использовать здесь и NumPy.ctypeslib. Мы'ре собирается построить *указатель типа*, что позволит нам пройти вокруг и NumPy.ndarrays
этих под
-загружен функции, как они были указатели. Здесь'ы код:
arr_1d_double = np.ctypeslib.ndpointer(dtype=np.double,
ndim=1,
flags='CONTIGUOUS')
haversine_lib.haversine.restype = ctypes.c_int
haversine_lib.haversine.argtypes = [ctypes.c_size_t,
arr_1d_double,
arr_1d_double,
arr_1d_double,
arr_1d_double,
arr_1d_double]
Обратите внимание, что мы говорим `haversine_lib.функции прокси-гаверсинус интерпретировать свои доводы по видам мы хотим.
Теперь, чтобы проверить его из кожи питона то, что остается, это просто сделать размер переменная, а массив, в котором будут мутировавшие (как в коде C) должна содержать данные результата, то мы можем назвать:
size = len(lat1)
output = np.empty(size, dtype=np.double)
print "====="
print output
t2 = time.time()
res = haversine_lib.haversine(size, lon1, lat1, lon2, lat2, output)
t3 = time.time()
print t3 - t2, res
print type(output), output
Собираем все вместе в блок _основной ___ о `haversine.py теперь весь файл выглядит так:
import time
import ctypes
import numpy as np
from math import radians, cos, sin, asin, sqrt
def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = (np.sin(dlat/2)**2
+ np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2)**2)
c = 2 * np.arcsin(np.sqrt(a))
km = 6367 * c
return km
if __name__ == "__main__":
lat1 = 50.0 * np.random.rand(1000000)
lon1 = 50.0 * np.random.rand(1000000)
lat2 = 50.0 * np.random.rand(1000000)
lon2 = 50.0 * np.random.rand(1000000)
t0 = time.time()
r1 = haversine(lon1, lat1, lon2, lat2)
t1 = time.time()
print t1-t0, r1
lib_path = "/home/ely/programming/python/numpy_ctypes/haversine.so"
haversine_lib = ctypes.CDLL(lib_path)
arr_1d_double = np.ctypeslib.ndpointer(dtype=np.double,
ndim=1,
flags='CONTIGUOUS')
haversine_lib.haversine.restype = ctypes.c_int
haversine_lib.haversine.argtypes = [ctypes.c_size_t,
arr_1d_double,
arr_1d_double,
arr_1d_double,
arr_1d_double,
arr_1d_double]
size = len(lat1)
output = np.empty(size, dtype=np.double)
print "====="
print output
t2 = time.time()
res = haversine_lib.haversine(size, lon1, lat1, lon2, lat2, output)
t3 = time.time()
print t3 - t2, res
print type(output), output
Чтобы запустить его, который будет работать и времени на Python и под
версии и отдельно печатать некоторые итоги, мы можем просто сделать
python haversine.py
который отображает:
0.111340045929 [ 231.53695005 3042.84915093 169.5158946 ..., 1359.2656769
2686.87895954 3728.54788207]
=====
[ 6.92017600e-310 2.97780954e-316 2.97780954e-316 ...,
3.20676686e-001 1.31978329e-001 5.15819721e-001]
0.148446083069 0
<type 'numpy.ndarray'> [ 231.53675618 3042.84723579 169.51575588 ..., 1359.26453029
2686.87709456 3728.54493339]
Как и ожидалось, включает
версия немного быстрее (0,11 секунды для векторов длины 1 млн.), Но наши быстрые и грязные версии под `не сутулиться: респектабельный 0.148 секунд на одни и те же данные.
Позвольте'ы сравните это с наивной цикл принятия решений в Python:
from math import radians, cos, sin, asin, sqrt
def slow_haversine(lon1, lat1, lon2, lat2):
n = len(lon1)
kms = np.empty(n, dtype=np.double)
for i in range(n):
lon1_v, lat1_v, lon2_v, lat2_v = map(
radians,
[lon1[i], lat1[i], lon2[i], lat2[i]]
)
dlon = lon2_v - lon1_v
dlat = lat2_v - lat1_v
a = (sin(dlat/2)**2
+ cos(lat1_v) * cos(lat2_v) * sin(dlon/2)**2)
c = 2 * asin(sqrt(a))
kms[i] = 6367 * c
return kms
Когда я положил это в один и тот же файл в Python, как и другие, и времени на тот же миллион-элемент данных, я постоянно вижу время около 2.65 секунд на моей машине.
Поэтому, быстро переходя на ПОД
мы повышаем скорость примерно 18. Для многих расчетов, которые могут извлечь выгоду из доступа к голой, непрерывных данных, вы часто видите доходы гораздо выше, чем даже это.
Просто супер понятно, я нисколько не одобряя это как лучший вариант, чем просто с помощью включает в себя
. Это как раз и проблема, что включает в себя
был построен, чтобы решить, и поэтому домашнего пивоварения свой собственный под
код всякий раз, когда он (а) имеет смысл включить включает в себя
типы данных в ваше приложение и (B) существует простой способ, чтобы сопоставить свой код В включает в себя
эквиваленте, это не очень эффективно.
Но это's по-прежнему очень полезно знать, как сделать это для тех случаев, когда вы предпочитаете писать что-то в C еще называют это в Python, или ситуаций, когда зависимость от включает в себя
- это не практично (во встроенной системе, где включает в себя
не может быть установлен, например).
В случае, если через пакет scikit-учиться разрешено, я бы дал следующие возможности:
from sklearn.neighbors import DistanceMetric
dist = DistanceMetric.get_metric('haversine')
# example data
lat1, lon1 = 36.4256345, -5.1510261
lat2, lon2 = 40.4165, -3.7026
lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
X = [[lat1, lon1],
[lat2, lon2]]
kms = 6367
print(kms * dist.pairwise(X))
Тривиальное расширение @derricw'ы векторизированный Решение Вы можете использовать numba
для повышения производительности в ~2 раза практически без изменения кода. Для чисто численных расчетов, это должно, вероятно, быть использован для сравнения / тестирования и, возможно, более эффективные решения.
from numba import njit
@njit
def haversine_nb(lon1, lat1, lon2, lat2):
lon1, lat1, lon2, lat2 = np.radians(lon1), np.radians(lat1), np.radians(lon2), np.radians(lat2)
dlon = lon2 - lon1
dlat = lat2 - lat1
a = np.sin(dlat/2.0)**2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2.0)**2
return 6367 * 2 * np.arcsin(np.sqrt(a))
Бенчмаркинг по отношению к функции панд:
%timeit haversine_pd(df['lon1'], df['lat1'], df['lon2'], df['lat2'])
# 1 loop, best of 3: 1.81 s per loop
%timeit haversine_nb(df['lon1'].values, df['lat1'].values, df['lon2'].values, df['lat2'].values)
# 1 loop, best of 3: 921 ms per loop
Полный код бенчмаркинга:
import pandas as pd, numpy as np
from numba import njit
def haversine_pd(lon1, lat1, lon2, lat2):
lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
dlon = lon2 - lon1
dlat = lat2 - lat1
a = np.sin(dlat/2.0)**2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2.0)**2
return 6367 * 2 * np.arcsin(np.sqrt(a))
@njit
def haversine_nb(lon1, lat1, lon2, lat2):
lon1, lat1, lon2, lat2 = np.radians(lon1), np.radians(lat1), np.radians(lon2), np.radians(lat2)
dlon = lon2 - lon1
dlat = lat2 - lat1
a = np.sin(dlat/2.0)**2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2.0)**2
return 6367 * 2 * np.arcsin(np.sqrt(a))
np.random.seed(0)
lon1, lon2, lat1, lat2 = np.random.randn(4, 10**7)
df = pd.DataFrame(data={'lon1':lon1,'lon2':lon2,'lat1':lat1,'lat2':lat2})
km = haversine_pd(df['lon1'], df['lat1'], df['lon2'], df['lat2'])
km_nb = haversine_nb(df['lon1'].values, df['lat1'].values, df['lon2'].values, df['lat2'].values)
assert np.isclose(km.values, km_nb).all()
%timeit haversine_pd(df['lon1'], df['lat1'], df['lon2'], df['lat2'])
# 1 loop, best of 3: 1.81 s per loop
%timeit haversine_nb(df['lon1'].values, df['lat1'].values, df['lon2'].values, df['lat2'].values)
# 1 loop, best of 3: 921 ms per loop
Функция векторизации указывает, что "все аргументы должны быть равной длины и". Расширяя границы в "больших" в наборе данных, согласно это, можно эффективно найти расстояние всех i,j в пар элементов.
from random import uniform
import numpy as np
def new_haversine_np(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
dlon = lon2 - lon1[:,None]
dlat = lat2 - lat1[:,None]
a = np.sin(dlat/2.0)**2 + np.cos(lat1[:,None]) * np.cos(lat2) * np.sin(dlon/2.0)**2
c = 2 * np.arcsin(np.sqrt(a))
km = 6367 * c
return km
lon1 = [uniform(-180,180) for n in range(6)]
lat1 = [uniform(-90, 90) for n in range(6)]
lon2 = [uniform(-180,180) for n in range(4)]
lat2 = [uniform(-90, 90) for n in range(4)]
new = new_haversine_np(lon1, lat1, lon2, lat2)
for i in range(6):
for j in range(4):
print(i,j,round(new[i,j],2))
Некоторые из этих ответов на "закругления" и радиус Земли. Если вы проверить их с другого расстояния калькуляторов (таких как geopy), эти функции будут отключены.
Вы можете переключиться из Р=3959.87433 для преобразования постоянного ниже, если вы хотите получить ответ в милях.
Если вы хотите километрах, используйте Р= 6372.8
.
lon1 = -103.548851
lat1 = 32.0004311
lon2 = -103.6041946
lat2 = 33.374939
def haversine(lat1, lon1, lat2, lon2):
R = 3959.87433 # this is in miles. For Earth radius in kilometers use 6372.8 km
dLat = radians(lat2 - lat1)
dLon = radians(lon2 - lon1)
lat1 = radians(lat1)
lat2 = radians(lat2)
a = sin(dLat/2)**2 + cos(lat1)*cos(lat2)*sin(dLon/2)**2
c = 2*asin(sqrt(a))
return R * c
print(haversine(lat1, lon1, lat2, lon2))