0

一意のポイントの配列から始めて、それらのポイントNx2のDelaunayを見つけます。これは、へのインデックスで構成される配列です。各エッジに対応する重みの配列もあります。edgesMx2pointsMx1

Hetlandの著書「PythonAlgorithms-MasteringBasicAlgorithms inthePythonLanguage」のリスト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]の間のエッジの重みを返します。ab

変換の目標は、本で説明されている高速トラバーサルなどのアルゴリズムの一部を使用できるようにすることです。既存のデータ構造とこの構造の間で変換するには、次のようにします。

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

コードに不要な操作がたくさんあります。エッジ全体で 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)なので、かなりのスピードアップが見られると思います。

于 2012-07-25T18:41:31.230 に答える