8

私は驚いています：

import igraph
import random, time
start_time = time.time()
G = igraph.Graph(directed = True)
G.add_vertices(10000)
for i in range(30000):
   G.add_edge(random.randint(0,9999), random.randint(0,9999))
print "done in " + str(int(time.time() - start_time)) + " seconds"

返品は 63 秒で完了

その間

import igraph
import random, time
start_time = time.time()
G = igraph.Graph(directed = True)
G.add_vertices(10000)
edges = []
for i in range(30000):
    edges += [(random.randint(0,9999), random.randint(0,9999))]
G.add_edges(edges)
print "done in " + str(int(time.time() - start_time)) + " seconds"

リターンは 0 秒で完了します。プロジェクトの誰かが理由を知っていますか?

4

1 に答える 1

14

その理由は、igraph がインデックス付きのエッジ リストを C 層のデータ構造として使用するためです。インデックスを使用すると、特定の頂点の近傍を一定時間でクエリできます。これは、グラフがめったに変更されない場合には適していますが、エッジを追加または削除するたびにインデックスを更新する必要があるため、変更操作がクエリよりもはるかに頻繁に行われる場合は負担になります。そのため、 を呼び出すたびにadd_edge、igraph は内部データ構造のインデックスを再作成します。利点は、とにかくインデックスを再構築する必要がある場合、add_edgesほぼ同じコストで多くのエッジを追加できることです。したがって、最初のコード例ではインデックスを 30000 回再構築しますが、2 番目の例ではインデックスを 1 回だけ再構築します。

ところで、あなたがしていることは、 を使用してさらに高速に実行できますGraph.Erdos_Renyi(n=10000, m=30000)。

于 2012-12-20T16:01:07.890 に答える