与Networkx相比，图形工具出奇的慢 [英] Graph-tool surprisingly slow compared to Networkx

问题描述

查看了令人印象深刻的性能比较后，我决定尝试绘制图表-工具.因此，为了进行比较，我编写了使用这两个程序包生成随机树的代码.

After looking at the impressive performance comparison, I decided that I would give a try to graph-tool. So for comparison, I wrote codes to generate a random tree using both packages.

图形工具代码:

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代码:

The Networkx code:

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秒！我缺少明显的东西吗?

The graph-tool takes around 14 seconds on my 4-core machine whereas networkx takes less than 2 seconds on the same machine! Am I missing something obvious?

谢谢.

推荐答案

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

There is nothing surprising here. graph-tool achieves greater performance by off-loading main loops to C++. If all your main loops are in Python, it offers no advantage. The same is true for other libraries like numpy.

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

The proper way to achieve fast addition of edges is to let graph-tool perform the main loop. The network you are generating is a simple growth model, and can be achieved in graph-tool by calling:

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

在我的计算机上大约需要15毫秒，n = 5000.

which takes about 15 ms in my computer for n=5000.

还请注意，由于每次迭代时都会创建具有所有顶点的新列表，因此python代码的运行速度不必要地慢.一个更快的版本是:

Note also that your python code is unnecessarily slow, since you create new lists with all vertices at each iteration. A much faster version would be:

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值，一次而不是一个接一个地添加所有边的速度更快，即

For even larger values of n, it will be even faster to add all edges at once instead of one by one, i.e.

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)

这篇关于与Networkx相比，图形工具出奇的慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！