如何在Python中傳播樹節點

Question

我正在處理Python程序中的樹結構。 樹中的每個節點都有一個字典「sons」，其中的鍵包含弧信息，值爲 是兒子節點。問題是將節點列表傳播給他們的所有兒子。 我使用：

current_nodes = reduce(lambda s,x:s+x, map(lambda node:node.sons.values(),current_nodes),[]) 

哪裏current_nodes爲節點的初始（和更新的）名單。

我的程序花費大部分時間來執行這個減少操作。有更快的方法來實現嗎？

謝謝！

編輯： 嗨，只是讓你知道這些代碼： sum((node.sons.values() for node in current_nodes), []) 雖然Python的，是不是真的顯著快 - 如果節點 的名單很長（> 20000），傳播速度減慢不成比例，實際上， 非常慢。我不知道爲什麼。

然後我定義：

def Ext(nodes) 
    l=[] 
    for node in nodes: 
     l.extend(node.sons.values()) 
    return l 

然後我用：current_node = Ext(current_node)。 這種方法實際上要快得多。在處理列表連接時，我猜sum（）函數的效率不如列表的擴展方法。

Answer 1

from itertools import chain 
list(chain.from_iterable(node.sons.values() for node in current_nodes)) 

應該更快。 map和reduce對lambda s很慢。我不知道chain有多快;你可以嘗試

sum((node.sons.values() for node in current_nodes), []) 

以及。