Векторизация вычисления эвклидовых расстояний - NumPy

Question

Мой вопрос касается векторизации моего кода. У меня есть один массив, который содержит 3D-координату и один массив, который содержит информацию ребер, которые соединяют координаты:

In [8]:coords 
Out[8]: 
array([[ 11.22727013, 24.72620964, 2.02986932], 
     [ 11.23895836, 24.67577744, 2.04130101], 
     [ 11.23624039, 24.63677788, 2.04096866], 
     [ 11.22516632, 24.5986824 , 2.04045677], 
     [ 11.21166992, 24.56095695, 2.03898215], 
     [ 11.20334721, 24.5227356 , 2.03556442], 
     [ 11.2064085 , 24.48479462, 2.03098583], 
     [ 11.22059727, 24.44837189, 2.02649784], 
     [ 11.24213409, 24.41513252, 2.01979685]]) 

In [13]:edges 
Out[13]: 
array([[0, 1], 
     [1, 2], 
     [2, 3], 
     [3, 4], 
     [4, 5], 
     [5, 6], 
     [6, 7], 
     [7, 8],], dtype=int32) 

Теперь, я хотел бы вычислить сумму евклидова расстояния между координатами в массиве ребер , Например. Расстояние от координат [0] к координатам [1] + расстояние от координат [1] к координатам [2] .....

У меня есть следующий код, который делает работу:

def networkLength(coords, edges): 

    from scipy.spatial import distance 
    distancesNetwork = np.array([])  

    for i in range(edges.shape[0]): 
     distancesNetwork = np.append(distancesNetwork, distance.euclidean(coords[edges[i, 0]], coords[edges[i, 1]])) 

    return sum(distancesNetwork) 

Мне было интересно, можно ли векторизовать код, а не делать цикл. Что такое питонский способ сделать это? Большое спасибо!!

Answer 1

Подход № 1

Мы могли бы порезать из первого и второго столбцов вообще для индексации в coords вместо итерацию для каждого элемента вдоль них и выполнять евклидово расстояние вычисления, которые включает в себя поэлементное возведения в квадрат и суммируя по каждая строка, а затем получает элементный квадратный корень. Наконец, нам нужно суммировать все эти значения для одного скаляра, как показано в исходном коде.

Таким образом, одна Векторизованная реализация будет -

np.sqrt(((coords[edges[:, 0]] - coords[edges[:, 1]])**2).sum(1)).sum() 

Там есть встроенные в NumPy сделать эти вычислительные операции расстояния, как np.linalg.norm. Что касается производительности, я бы подумал, что это будет сопоставимо с тем, что мы только что упомянули ранее. Для полноты картины, реализация будет -

np.linalg.norm(coords[edges[:, 0]] - coords[edges[:, 1]],axis=1).sum() 

Подход № 2

Tweaking ранее подход, мы могли бы использовать np.einsum, что в одном шаге будет выполнять как squaring и summing along each row и как таковой будет быть немного более эффективным.

Реализация будет выглядеть примерно так -

s = coords[edges[:, 0]] - coords[edges[:, 1]] 
out = np.sqrt(np.einsum('ij,ij->i',s,s)).sum() 

---

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

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

def networkLength(coords, edges): # Original code from question 
    distancesNetwork = np.array([])  
    for i in range(edges.shape[0]): 
     distancesNetwork = np.append(distancesNetwork, \ 
     distance.euclidean(coords[edges[i, 0]], coords[edges[i, 1]])) 
    return sum(distancesNetwork) 

def vectorized_app1(coords, edges): 
    return np.sqrt(((coords[edges[:, 0]] - coords[edges[:, 1]])**2).sum(1)).sum() 

def vectorized_app2(coords, edges): 
    s = coords[edges[:, 0]] - coords[edges[:, 1]] 
    return np.sqrt(np.einsum('ij,ij->i',s,s)).sum() 

Проверка и Timings -

In [114]: # Setup bigger inputs 
    ...: coords = np.random.rand(100,3) 
    ...: edges = np.random.randint(0,100,(10000,2)) 

# Verify results across all approaches 
In [115]: networkLength(coords, edges) 
Out[115]: 6607.8829431403547 

In [116]: vectorized_app1(coords, edges) 
Out[116]: 6607.8829431403337 

In [117]: vectorized_app2(coords, edges) 
Out[117]: 6607.8829431403337 

In [118]: %timeit networkLength(coords, edges) 
    ...: %timeit vectorized_app1(coords, edges) 
    ...: %timeit vectorized_app2(coords, edges) 
    ...: 
1 loops, best of 3: 519 ms per loop 
1000 loops, best of 3: 822 µs per loop 
1000 loops, best of 3: 668 µs per loop