0

我从一组独特的点开始，然后找到这些点Nx2的 Delaunay ，这是一个由索引组成的数组。还有一个与每条边相对应的权重数组。edgesMx2pointsMx1

我正在尝试将数据放入 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

这在大型集合上相当耗时（即在 > 15,000 个顶点上大约需要 40 秒）并且成为代码中的瓶颈。如何G更快地转换为数据结构？

编辑：

仅供参考，使用matplotlib.delaunay.delaunay()输出中心、边、三角形和邻居，这可能很有用。但是，我还没有想出如何将它们用于此目的。

4

1 回答 1

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)to减少O(E)，因此我希望您会看到相当大的加速。

于 2012-07-25T18:41:31.230 回答