与Networkx相比,Graph-tool的速度惊人地慢

Question

在看了令人印象深刻的性能比较后,我决定尝试使用图形工具.因此,为了进行比较,我编写了代码以使用两个包生成随机树.

图形工具代码:

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这样的其他库也是如此.

实现边缘快速添加的正确方法是让图形工具执行主循环.您生成的网络是一个简单的增长模型,可以通过调用以下方式在图形工具中实现:

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)