Векторизация вычисления расстояния Haversine в Python

Я пытаюсь вычислить матрицу расстояний для длинного списка местоположений, обозначенных Latitude & Longitude, используя формулу Хаверсина, которая берет два кортежа пар координат для создания расстояния:

def haversine(point1, point2, miles=False): """ Calculate the great-circle distance bewteen two points on the Earth surface. :input: two 2-tuples, containing the latitude and longitude of each point in decimal degrees. Example: haversine((45.7597, 4.8422), (48.8567, 2.3508)) :output: Returns the distance bewteen the two points. The default unit is kilometers. Miles can be returned if the ``miles`` parameter is set to True. """ 

Я могу рассчитать расстояние между всеми точками, используя замкнутый цикл:

 data.head() id coordinates 0 1 (16.3457688674, 6.30354512503) 1 2 (12.494749307, 28.6263955635) 2 3 (27.794615136, 60.0324947881) 3 4 (44.4269923769, 110.114216113) 4 5 (-69.8540884125, 87.9468778773) 

используя простую функцию:

 distance = {} def haver_loop(df): for i, point1 in df.iterrows(): distance[i] = [] for j, point2 in df.iterrows(): distance[i].append(haversine(point1.coordinates, point2.coordinates)) return pd.DataFrame.from_dict(distance, orient='index') 

Но это занимает довольно много времени, учитывая временную сложность, и работает около 20 секунд на 500 пунктов, и у меня есть намного более длинный список. Это приводит меня к векторизации, и я столкнулся с numpy.vectorize ( (docs) , но не могу понять, как применить его в этом контексте.

3 Solutions collect form web for “Векторизация вычисления расстояния Haversine в Python”

Вы предоставили бы свою функцию в качестве аргумента для np.vectorize() , а затем могли бы использовать ее в качестве аргумента для pandas.groupby.apply как показано ниже:

 haver_vec = np.vectorize(haversine, otypes=[np.int16]) distance = df.groupby('id').apply(lambda x: pd.Series(haver_vec(df.coordinates, x.coordinates))) 

Например, с данными выборки следующим образом:

 length = 500 df = pd.DataFrame({'id':np.arange(length), 'coordinates':tuple(zip(np.random.uniform(-90, 90, length), np.random.uniform(-180, 180, length)))}) 

сравнить за 500 очков:

 def haver_vect(data): distance = data.groupby('id').apply(lambda x: pd.Series(haver_vec(data.coordinates, x.coordinates))) return distance %timeit haver_loop(df): 1 loops, best of 3: 35.5 s per loop %timeit haver_vect(df): 1 loops, best of 3: 593 ms per loop 

Из haversine's function definition оно выглядело довольно параллелизуемым . Итак, используя один из лучших инструментов для векторизации с NumPy aka, broadcasting и заменяющий математические функции эквивалентами NumPy ufuncs , вот одно векторное решение –

 # Get data as a Nx2 shaped NumPy array data = np.array(df['coordinates'].tolist()) # Convert to radians data = np.deg2rad(data) # Extract col-1 and 2 as latitudes and longitudes lat = data[:,0] lng = data[:,1] # Elementwise differentiations for lattitudes & longitudes diff_lat = lat[:,None] - lat diff_lng = lng[:,None] - lng # Finally Calculate haversine d = np.sin(diff_lat/2)**2 + np.cos(lat[:,None])*np.cos(lat) * np.sin(diff_lng/2)**2 return 2 * 6371 * np.arcsin(np.sqrt(d)) 

Тесты времени выполнения –

np.vectorize based solution , показало некоторые положительные перспективы по улучшению производительности по сравнению с исходным кодом, поэтому в этом разделе будет сопоставлен подход, основанный на широковещательном доступе к этому.

Определения функций –

 def vectotized_based(df): haver_vec = np.vectorize(haversine, otypes=[np.int16]) return df.groupby('id').apply(lambda x: pd.Series(haver_vec(df.coordinates, x.coordinates))) def broadcasting_based(df): data = np.array(df['coordinates'].tolist()) data = np.deg2rad(data) lat = data[:,0] lng = data[:,1] diff_lat = lat[:,None] - lat diff_lng = lng[:,None] - lng d = np.sin(diff_lat/2)**2 + np.cos(lat[:,None])*np.cos(lat) * np.sin(diff_lng/2)**2 return 2 * 6371 * np.arcsin(np.sqrt(d)) 

Сроки –

 In [123]: # Input ...: length = 500 ...: d1 = np.random.uniform(-90, 90, length) ...: d2 = np.random.uniform(-180, 180, length) ...: coords = tuple(zip(d1, d2)) ...: df = pd.DataFrame({'id':np.arange(length), 'coordinates':coords}) ...: In [124]: %timeit vectotized_based(df) 1 loops, best of 3: 1.12 s per loop In [125]: %timeit broadcasting_based(df) 10 loops, best of 3: 68.7 ms per loop 

начните с получения всех комбинаций, используя itertools.product

  results= [(p1,p2,haversine(p1,p2))for p1,p2 in itertools.product(points,repeat=2)] 

что я не уверен, насколько быстро это будет похоже на то, что это может быть дубликат Python: ускорение географического сравнения

Python - лучший язык программирования в мире.