我有以下代码:
import networkx
def reverse_graph(g):
reversed = networkx.DiGraph()
for e in g.edges():
reversed.add_edge(e[1], e[0])
return reversed
g = networkx.DiGraph()
for i in range(500000):
g.add_edge(i, i+1)
g2 = g.reverse()
g3 = reverse_graph(g)
根据我的线路分析器,我花费了更多时间使用 networkx 来反转图形(他们的反转大约需要 21 秒,我的大约需要 7 秒)。在这个简单的例子中,开销似乎很高,而在我拥有的其他代码中更复杂的对象更糟。 networkx 背后是否发生了一些我不知道的事情?这看起来应该是一个相对便宜的功能。
作为引用,这里是 doc对于 reverse 函数
编辑: 我还尝试以相反的方式运行实现(即首先是我的实现)以确保在他们创建自己的实现时没有发生缓存。我的仍然明显更快
请您参考如下方法:
The source code for the reverse method看起来像这样:
def reverse(self, copy=True):
"""Return the reverse of the graph.
The reverse is a graph with the same nodes and edges
but with the directions of the edges reversed.
Parameters
----------
copy : bool optional (default=True)
If True, return a new DiGraph holding the reversed edges.
If False, reverse the reverse graph is created using
the original graph (this changes the original graph).
"""
if copy:
H = self.__class__(name="Reverse of (%s)"%self.name)
H.add_nodes_from(self)
H.add_edges_from( (v,u,deepcopy(d)) for u,v,d
in self.edges(data=True) )
H.graph=deepcopy(self.graph)
H.node=deepcopy(self.node)
else:
self.pred,self.succ=self.succ,self.pred
self.adj=self.succ
H=self
return H
所以默认情况下,当copy=True时,不仅边缘节点被反转, 而且还会对任何边缘数据进行深度复制。然后图形属性(保存在 self.graph) 被深度复制,然后节点本身被深度复制。 这是 reverse_graph 做不到的大量复制。
如果您不对所有内容进行深度复制,修改 g3 可能会影响 g。
如果您不需要对所有内容进行深度复制,(并且可以接受变异 g),那么
g.reverse(copy=False)
比
还要快g3 = reverse_graph(g)
In [108]: %timeit g.reverse(copy=False)
1000000 loops, best of 3: 359 ns per loop
In [95]: %timeit reverse_graph(g)
1 loops, best of 3: 1.32 s per loop
In [96]: %timeit g.reverse()
1 loops, best of 3: 4.98 s per loop
