python - networkx 反向函数的开销？

Question

我有以下代码:

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 函数

编辑: 我还尝试以相反的方式运行实现(即首先是我的实现)以确保在他们创建自己的实现时没有发生缓存。我的仍然明显更快

Answer 1

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