векторизация Haversine в Python

Question

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

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), но не могу понять, как применять его в этом контексте.

Answer 1

Вы бы обеспечить вашу функцию в качестве аргумента 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 

Answer 2

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

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

, что сказал я не уверен, как быстро он будет это выглядит, как он может быть дубликатом Python: speeding up geographic comparison

Answer 3

От haversine's function definition, это выглядело довольно параллелизуемый. Таким образом, используя один из лучших инструментов для векторизации с NumPy аки broadcasting и заменяя математическую funcs с эквивалентами 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