14

在查看了令人印象深刻的性能比较之后，我决定尝试使用图形工具。因此，为了比较，我编写了代码来使用这两个包生成随机树。

图形工具代码：

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 秒！我错过了一些明显的东西吗？

提前致谢。

4

1 回答 1

28

这里没有什么令人惊讶的。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)
于 2016-03-24T14:31:07.580 回答