Numpy：将矩阵的每一行添加到矩阵中（一次一行），然后找到每个新矩阵中每行的最小值。希望加快编码速度

Question

我把矩阵的每一行加到矩阵中，然后计算新矩阵中每行的最小值。在

我当前使用的python代码包含一个测试用例：

# Compute distances to all other nodes using landmarks 
distToLM = np.array([[1,2,3],[4,5,6],[7,8,9]])
m = len(distToLM)
count = 1
dist = np.zeros((m,m))
for i in range(m):
    findMin = distToLM[i,:] + distToLM.take(range(count,m),axis=0) 
    dist[i,count:]=np.min(findMin,axis = 1)
    count = count + 1

注意：我每次切片矩阵，因为我只需要矩阵的上三角值

所以第一次迭代会将[1,2,3]加到[4,5,6]和[7,8,9]上，从而形成一个矩阵：

[5,7,9]

[8,10,12]

从这里开始，我要每行的最小值，所以5和8。在

下一次迭代我将取[4,5,6]并将其添加到它下面的所有行中，即[7,8,9]，并取每行的最小值。在

这个代码相当慢，对于4000x4000矩阵来说大约是3秒。在

我也尝试过Cython版本，速度没有太大的提高，可能是因为它严重依赖于调用numpy函数，而不是用C执行主代码：

^{pr2}$

我想如果有什么方法可以向量化它会快得多。在

我愿意接受任何建议。在

Answer 1

稍微改变一下有助于我更好地可视化操作（我很少使用take）：

distToLM = np.array([[1,2,3],[4,5,6],[7,8,9]])
m = distToLM.shape[0]
dist = np.zeros((m,m), distToLM.dtype)
for i in range(m):
    findMin = distToLM[i,:] + distToLM[i+1:,:] 
    dist[i, i+1:] = np.min(findMin,axis = 1)

事实上，双重迭代甚至很清楚：

^{pr2}$

这揭示了代码中模糊的2维对称性。这不是更快，但将更容易实现与cythonmemoryviews。在

这种对称性还表明我可以对这些行执行“外部”求和：

In [512]: np.min(distToLM[:,None,:]+distToLM[None,:,:],axis=-1)
Out[512]: 
array([[ 2,  5,  8],
       [ 5,  8, 11],
       [ 8, 11, 14]])

上三角是所需的距离

In [518]: np.triu(_,k=1)
Out[518]: 
array([[ 0,  5,  8],
       [ 0,  0, 11],
       [ 0,  0,  0]])

这比迭代方法计算更多的值，但可能更快。不幸的是，对于您的大问题，中等大小（400040004000）数组可能对内存来说太大了。在

我可以先选择triu索引，然后再使用：

In [530]: I,J=np.triu_indices(3,1)
In [531]: I,J
Out[531]: (array([0, 0, 1], dtype=int32), array([1, 2, 2], dtype=int32))
In [532]: np.min(distToLM[I,:]+distToLM[J,:],axis=1)
Out[532]: array([ 5,  8, 11])

我不知道如何在大型数组中执行。在

这提醒了我，scipy.spatial有它所称的squareform和{}成对距离的表示。在

https://docs.scipy.org/doc/scipy/reference/spatial.distance.html

也许那里有些有用的东西。在