向量化欧式距离计算 - 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)

我想知道是否可以矢量化代码，而不是进行循环。 pythonian 的方法是什么？非常感谢！！

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

调整较早的方法，我们可以使用 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

向量化欧式距离计算 - NumPy

Vectorizing euclidean distance computation - NumPy

python

numpy

vectorization

scipy

euclidean-distance