Estoy tratando de calcular una matriz de distancias para una larga lista de ubicaciones identificadas por Latitud y Longitud utilizando la fórmula de Haversine que toma dos tuplas de pares de coordenadas para producir la distancia:
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. """ Puedo calcular la distancia entre todos los puntos usando un bucle nested para:
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)
utilizando una función simple:
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')
Pero esto toma bastante tiempo dada la complejidad del tiempo, se ejecuta alrededor de los 20 por 500 puntos y tengo una lista mucho más larga. Esto me hace ver la vectorización, y me he topado con numpy.vectorize ( (docs) , pero no numpy.vectorize cómo aplicarlo en este contexto).
np.vectorize() proporcionar su función como un argumento a np.vectorize() , y luego podría usarla como un argumento para pandas.groupby.apply como se ilustra a continuación:
haver_vec = np.vectorize(haversine, otypes=[np.int16]) distance = df.groupby('id').apply(lambda x: pd.Series(haver_vec(df.coordinates, x.coordinates)))
Por ejemplo, con datos de muestra de la siguiente manera:
length = 500 df = pd.DataFrame({'id':np.arange(length), 'coordinates':tuple(zip(np.random.uniform(-90, 90, length), np.random.uniform(-180, 180, length)))})
comparar por 500 puntos:
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
Desde haversine's function definition , se veía bastante paralelizable . Por lo tanto, al utilizar una de las mejores herramientas de vectorización con NumPy al igual que la broadcasting y al reemplazar las funciones matemáticas con los equivalentes NumPy ufuncs , aquí hay una solución vectorizada:
# 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))
Pruebas de tiempo de ejecución
La otra np.vectorize based solution ha mostrado cierta promesa positiva en cuanto a la mejora del rendimiento con respecto al código original, por lo que esta sección comparará el enfoque basado en la difusión publicado con ese.
Definiciones de funciones –
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))
Tiempos –
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
Comience por obtener todas las combinaciones usando itertools.product
results= [(p1,p2,haversine(p1,p2))for p1,p2 in itertools.product(points,repeat=2)]
Dicho esto, no estoy seguro de qué tan rápido será este aspecto, podría ser un duplicado de Python: acelerando la comparación geográfica