igraph:为什么add_edge函数比add_edges这么慢? [英] igraph: why is add_edge function so slow ompared to add_edges?

问题描述

我很惊讶:

import igraph
import random, time
start_time = time.time()
G = igraph.Graph(directed = True)
G.add_vertices(10000)
for i in range(30000):
   G.add_edge(random.randint(0,9999), random.randint(0,9999))
print "done in " + str(int(time.time() - start_time)) + " seconds"

63秒内完成返回

同时

import igraph
import random, time
start_time = time.time()
G = igraph.Graph(directed = True)
G.add_vertices(10000)
edges = []
for i in range(30000):
    edges += [(random.randint(0,9999), random.randint(0,9999))]
G.add_edges(edges)
print "done in " + str(int(time.time() - start_time)) + " seconds"

在0秒内完成返回. 项目中的某人知道为什么吗?

returns done in 0 seconds. Does someone from the project know why?

推荐答案

原因是igraph在C层中使用索引边缘列表作为其数据结构.索引使得可以在恒定时间内查询特定顶点的邻居.如果图形很少更改，则很好，但是当修改操作比查询频繁得多时，它将成为负担，因为无论何时添加或删除边，都必须更新索引.因此，每次调用add_edge都会使igraph重新为其内部数据结构编制索引.好处是，如果您仍然必须重建索引，则可以使用add_edges以几乎相同的成本添加许多边.因此，在第一个代码示例中，您重建索引30000次，而在第二个示例中，您仅重建索引一次.

The reason is that igraph uses an indexed edge list as its data structure in the C layer. The index makes it possible to query the neighbors of a specific vertex in constant time. This is good if your graph rarely changes, but it becomes a burden when the modification operations are far more frequent than the queries, since whenever you add or remove an edge, you have to update the index. So, every call to add_edge will make igraph reindex its internal data structures. The upside is that if you have to rebuild the index anyway, you can just as well add many edges using add_edges with approximately the same cost. So, in your first code example, you rebuild the index 30000 times, while in the second example, you rebuild the index only once.

顺便说一句，使用Graph.Erdos_Renyi(n=10000, m=30000)可以更快地完成您的工作.

By the way, what you are doing could be done even faster using Graph.Erdos_Renyi(n=10000, m=30000).

这篇关于igraph:为什么add_edge函数比add_edges这么慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！