python - 与 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)))

图形工具在我的 4 核机器上花费大约 14 秒，而 networkx 在同一台机器上花费不到 2 秒!我是否遗漏了一些明显的东西？

提前致谢。

Answer 1

这里没有什么奇怪的。 graph-tool 通过将主循环卸载到 C++ 来实现更高的性能。如果您所有的主循环都在 Python 中，则它没有任何优势。对于 numpy 等其他库也是如此。

实现快速添加边的正确方法是让graph-tool执行主循环。您正在生成的网络是一个简单的增长模型，可以通过调用图形工具来实现:

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

对于 n=5000，这在我的计算机上大约需要 15 毫秒。

另请注意，您的 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)