Skip to main content
 首页 » 编程设计

python之networkx 反向函数的开销

2024年10月25日15xing901022

我有以下代码:

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