快速生成图形结构

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和{}之间的边的权重。在

转换的目标是能够使用一些快速遍历等算法，在书中也有描述。要在现有数据结构和此结构之间进行转换，请执行以下操作：

^{pr2}$

这在大型集合上相当耗时（即在15000个顶点上大约需要40秒），并成为代码的瓶颈。如何更快地转换为数据结构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)减少到{}，因此我希望您能看到相当大的加速。在