GraphxはNetworkxに比べて驚くほど遅い

Question

印象的なperformance comparisonを見てから、グラフツールを試してみることにしました。比較のために、私は両方のパッケージを使用してランダムなツリーを生成するコードを書きました。

グラフツールコード：

import numpy as np 
import graph_tool.all as gt 

# construct an initial graph with two nodes and one link 
n = 5000 
G = gt.Graph(directed = False) 
G.add_edge(0, 1) 

for t in range(2, n): 
    # connect the new vertex to one of the old vertices randomly 
    G.add_edge(np.random.choice(range(t)), t) 

Networkxコード：

import networkx as nx 
import numpy as np 

n = 5000 
# initial graph 
G = nx.Graph() 
G.add_edge(0, 1) 

for t in range(2, n): 
    G.add_edge(t, np.random.choice(range(t))) 

networkxがオン2秒未満を要するのに対し、グラフツールは、私の4コアマシン上で約14秒かかり同じマシン！私は明白な何かを欠いていますか

ありがとうございます。

Answer 1

ここには何も驚くことはありません。 graph-toolは、メインループをC++にロードすることにより、より大きなパフォーマンスを実現します。すべてのメインループがPythonに含まれていれば、利点はありません。 numpyのような他のライブラリについても同じことが当てはまります。

エッジの高速追加を実現する適切な方法は、graph-toolにメインループを実行させることです。あなたが生成しているネットワークは、単純な成長モデルで、呼び出すことで、グラフツールで達成することができます。

N = 5000のための私のコンピュータでは約15ミリ秒かかり

G = price_network(n, gamma=0, directed=False) 

。

各繰り返しですべての頂点を持つ新しいリストを作成するので、Pythonコードが不必要に遅いことにも注意してください。はるかに高速バージョンは次のようになります。

from numpy.random import randint 
n = 5000 
G = Graph(directed=False) 
G.add_vertex(n) 
G.add_edge(0, 1) 
for i in range(2, n): 
    G.add_edge(i, randint(i)) 

n個のより大きな値の場合、それは私が追加することを推測すなわち、

from graph_tool.all import * 
from numpy.random import randint 
n = 5000 
G = Graph(directed=False) 
edges = [(0, 1)] 
for i in range(2, n): 
    edges.append((i, randint(i))) 
G.add_edge_list(edges)