用numpy数组索引加速边缘矩阵的获取

Question

我想切割原始矩阵的边缘，并想知道是否有一个更快的方法。由于我需要使用相同的位置和positions_u多次运行selectEdge函数，这意味着索引对于许多图不会改变吗？是否有可能生成一个映射矩阵，可以为所有人修复？

非常感谢

def selectEdge(positions, positions_u, originalMat, selectedMat):
    """ select Edge by neighbors of all points
    many to many
    m positions
    n positions
    would have m*n edges
    update selectedMat
    """
    for ele in positions:
        for ele_u in positions_u:            
            selectedMat[ele][ele_u] += originalMat[ele][ele_u]
            selectedMat[ele_u][ele] += originalMat[ele_u][ele]
    return selectedMat

我只需要上三角矩阵，因为它是对称的。

def test_selectEdge(self):
        positions, positions_u = np.array([0,1,5,7]), np.array([2,3,4,6])
        originalMat, selectedMat = np.array([[1.0]*8]*8), np.array([[0.0]*8]*8)
        selectedMat = selectEdge(positions, positions_u, originalMat, selectedMat)
        print 'position, positions_u'
        print positions, positions_u
        print 'originalMat', originalMat
        print 'selectedMat', selectedMat

这是我的测试结果

position, positions_u
[0 1 5 7] [2 3 4 6]
originalMat 
[[ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.]]
selectedMat 
[[ 0.  0.  1.  1.  1.  0.  1.  0.]
 [ 0.  0.  1.  1.  1.  0.  1.  0.]
 [ 1.  1.  0.  0.  0.  1.  0.  1.]
 [ 1.  1.  0.  0.  0.  1.  0.  1.]
 [ 1.  1.  0.  0.  0.  1.  0.  1.]
 [ 0.  0.  1.  1.  1.  0.  1.  0.]
 [ 1.  1.  0.  0.  0.  1.  0.  1.]
 [ 0.  0.  1.  1.  1.  0.  1.  0.]]

对于后一种选择近邻边的实现，它的速度会更慢。

def selectNeighborEdges(originalMat, selectedMat, relation):
    """ select Edge by neighbors of all points
    one to many
    Args:
        relation: dict, {node1:[node i, node j,...], node2:[node i, node j, ...]}

    update selectedMat
    """
    for key in relation:
        selectedMat = selectEdge([key], relation[key], originalMat, selectedMat)
    return selectedMat

Answer 1

可以使用for-loop消除双重“高级整数索引”。

X, Y = positions[:,None], positions_u[None,:]
selectedMat[X, Y] += originalMat[X, Y]
selectedMat[Y, X] += originalMat[Y, X]

例如,

import numpy as np

def selectEdge(positions, positions_u, originalMat, selectedMat):
    for ele in positions:
        for ele_u in positions_u:
            selectedMat[ele][ele_u] += originalMat[ele][ele_u]
            selectedMat[ele_u][ele] += originalMat[ele_u][ele]
    return selectedMat

def alt_selectEdge(positions, positions_u, originalMat, selectedMat):
    X, Y = positions[:,None], positions_u[None,:]
    selectedMat[X, Y] += originalMat[X, Y]
    selectedMat[Y, X] += originalMat[Y, X]
    return selectedMat


N, M = 100, 50
positions = np.random.choice(np.arange(N), M, replace=False)
positions_u = np.random.choice(np.arange(N), M, replace=False)
originalMat = np.random.random((N, N))
selectedMat = np.zeros_like(originalMat)

首先检查selectEdge和alt_selectEdge是否返回相同的结果：

expected = selectEdge(positions, positions_u, originalMat, selectedMat)
result = alt_selectEdge(positions, positions_u, originalMat, selectedMat)
assert np.allclose(expected, result)

下面是一个timeit基准测试(使用IPython)：

In [89]: %timeit selectEdge(positions, positions_u, originalMat, selectedMat)
100 loops, best of 3: 4.44 ms per loop

In [90]: %timeit alt_selectEdge(positions, positions_u, originalMat, selectedMat)
10000 loops, best of 3: 104 µs per loop