加速通過索引與numpy數組獲得邊緣矩陣

Question

我想切割原始矩陣中的邊緣，並想知道有沒有更快的方法。因爲我需要用相同的位置和位置_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

您可以通過使用"advanced integer indexing"消除雙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) 

這裏是（使用IPython的）一個timeit基準：

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