更快的圖結構生成

Question

我以Nx2排列的唯一點開始，然後找到這些點的Delaunay edges，由索引到points組成的Mx2數組。還有一個Mx1對應於每個邊的權重陣列。

我想將數據轉換爲Hetland的書籍「Python算法 - 掌握Python語言中的基本算法」的清單2.3中描述的結構。結構是：

a, b, c, d, e, f, g, h = range(8) 
G = [ 
    {b:2, c:1, d:3, e:9, f:4}, # a 
    {c:4, e:3}, # b 
    {d:8}, # c 
    {e:7}, # d 
    {f:5}, # e 
    {c:2, g:2, h:2}, # f 
    {f:1, h:6}, # g 
    {f:9, g:8} # h 
] 

其中G[a]返回邊緣入射到點a和G[a][b]返回邊緣的a和b之間的重量。

轉換的目標是能夠使用本書中描述的一些快速遍歷等算法。爲了將現有的數據結構和該結構之間的轉換，我做的：

def make_graph(points, edges, weights): 
    G = [] 
    for i in range(len(points)): 
     w = numpy.where(edges == i) 
     d = {} 
     for ind,j in enumerate(edges[w[0],~w[1]]): 
      d[j] = weights[w[0][ind]] 
     G.append(d) 
    return G 

這是相當費時的大集（即大概需要40秒> 15000個頂點），併成爲在代碼中的瓶頸。我怎樣才能更快地將數據結構G轉換成？

編輯：

僅供參考，使用matplotlib.delaunay.delaunay()輸出中心，邊緣，三角形和鄰居，這可能是有用的。但是，我還沒有想到如何將它們用於此目的。

Answer 1

你的代碼中有很多不必要的操作。你可以做整個事情在一個迭代在邊緣：

G = [{} for i in range(len(points))] 
for i,e in enumerate(edges): 
    G[e[0]][e[1]] = weights[i] 
return G 

這應該從O(P*E)運行時減少O(E)，所以我希望你能看到一個相當大的加速。