Ускорение простого вычисления расстояния

Question

Я реализую простой код, который вычисляет расстояние между точкой (x_a, y_a) в list_A и всеми точками (x_b, y_b) в list_B и возвращает минимальное найденное расстояние. Это повторяется для всех точек в list_A.

А MWE моего кода:

# list_A points defined in array. 
list_A = np.array([ 
    [x_data_a, # x 
    y_data_a] # y 
    ], dtype=float) 

# list_B points defined in list. 
list_B = [[x_data_b], [y_data_b]] 

# Iterate through all data points in list_A 
for ind, x_a in enumerate(list_A[0][0]): 
    y_a = list_A[0][1][ind] 

    # Iterate through all points in list_B. 
    dist_min = 1000. 
    for ind2, x_b in enumerate(list_B[0]): 
     y_b = list_B[1][ind2] 
     # Find distance between points. 
     dist = (x_a-x_b)**2 + (y_a-y_b)**2 
     if dist < dist_min: 
      # Update value of min distance. 
      dist_min = dist 

    print 'Min dist to (', x_a, y_a, '): ', dist_min 

Данные отформатирован следующим образом:

list_A = [[[1.2 2.3 1.5 2.3 5.8 4.6 9.1] [2.5 1.0 4.6 2.4 7.4 1.1 3.2]]] 

list_B = [[1.4, 5.8, 7.9], [6.1, 1.2, 3.7]] 

Для больших списков/массивов это может занять некоторое время, чтобы закончить. Можно ли это ускорить?

Answer 1

Запуск кода я получаю следующее:

Min dist to (1.2 2.5): 13.0 
Min dist to (2.3 1.0): 12.29 
Min dist to (1.5 4.6): 2.26 
Min dist to (2.3 2.4): 13.69 
Min dist to (5.8 7.4): 18.1 
Min dist to (4.6 1.1): 1.45 
Min dist to (9.1 3.2): 1.69 

Преобразование вашего массива в следующих NX2 массивов:

a 
[[ 1.2 2.5] 
[ 2.3 1. ] 
[ 1.5 4.6] 
[ 2.3 2.4] 
[ 5.8 7.4] 
[ 4.6 1.1] 
[ 9.1 3.2]] 

b 
[[ 1.4 6.1] 
[ 5.8 1.2] 
[ 7.9 3.7]] 

Теперь должно работать:

import scipy.spatial.distance as spdist 

dist_arr = spdist.cdist(a,b) 

print dist_arr**2 
[[ 13. 22.85 46.33] 
[ 26.82 12.29 38.65] 
[ 2.26 30.05 41.77] 
[ 14.5 13.69 33.05] 
[ 21.05 38.44 18.1 ] 
[ 35.24 1.45 17.65] 
[ 67.7 14.89 1.69]] 

ind = np.argmin(dist_arr,axis=1) 

print ind 
[0 1 0 1 2 1 2] 

print dist_arr[np.arange(ind.shape[0]),ind]**2 
[ 13. 12.29 2.26 13.69 18.1 1.45 1.69] 

принимает ~ .3 секунды, если a и b - 2X5000 против 135 секунд с исходным кодом. Ускорение 450 раз.

Answer 2

Используйте scipy.spatial.distance.cdist, и вам не нужно писать собственный код расчета расценок.

Редактировать: вам необходимо перенести данные. Он должен быть в таком формате:

list_A = [ 
[1, 2], 
[3, 4], 
[4, 5] 
] 

list_B = [ 
[8, 9], 
[10, 11], 
[11, 12], 
[13, 14] 
] 

В настоящее время у вас есть список координат X и отдельный список координат Y. Вам нужно переориентировать их, чтобы у вас был один список пар XY. Если ваши данные являются обычными списками, вы можете транспонировать их с помощью list_A = zip(*list_A); если они являются массивными массивами, вы можете транспонировать их с помощью list_A = list_A.T.

Answer 3

Если вы хотите, чтобы избежать использования SciPy получить scipy.spatial.dist

import numpy as np 

a = np.random.rand(2,1000) 
b = np.random.rand(2,1001) 

min_dist = np.sqrt(np.min([np.min(np.sum((b - a[:,i,None])**2, axis=0)) 
          for i in range(a.shape[1])])) 

Если вы ищете мин дист для каждой точки а, а затем заменить последнюю строку с

min_dists = np.sqrt([np.min(np.sum((b - a[:,i,None])**2, axis=0)) 
          for i in range(a.shape[1])])