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

Question

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

Мой вопрос касается векторизации моего кода. У меня есть один массив, который содержит 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)

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

762 1

python numpy scipy vectorization

1 ответ:

Comments

Ничего не найдено.

Divakar · Accepted Answer · 2016-12-18 21:46:02

Подход #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

Корректируя предыдущий подход, мы могли бы использовать 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()
Проверка и тайминги -
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