与 Networkx 相比,图形工具出奇地慢
Graph-tool surprisingly slow compared to Networkx
看了令人印象深刻的 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 秒!我是否漏掉了一些明显的东西?
提前致谢。
这里没有什么奇怪的。 graph-tool 通过将主循环卸载到 C++ 来实现更高的性能。如果您所有的主循环都在 Python 中,则它没有任何优势。对于像 numpy 这样的其他库也是如此。
实现快速添加边的正确方法是让graph-tool执行主循环。您正在生成的网络是一个简单的增长模型,可以通过调用 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)
看了令人印象深刻的 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 秒!我是否漏掉了一些明显的东西?
提前致谢。
这里没有什么奇怪的。 graph-tool 通过将主循环卸载到 C++ 来实现更高的性能。如果您所有的主循环都在 Python 中,则它没有任何优势。对于像 numpy 这样的其他库也是如此。
实现快速添加边的正确方法是让graph-tool执行主循环。您正在生成的网络是一个简单的增长模型,可以通过调用 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)