python - 如何在 Python 中传播树节点

Question

我正在处理 Python 程序中的树结构。树中的每个节点都有一个字典“sons”，其键保存弧信息，和值是子节点。问题是将节点列表传播给他们所有的儿子。我使用:

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

其中 current_nodes 是节点的初始(和更新)列表。

我的程序大部分时间都在执行这个 reduce 操作。有没有更快的方法来实现它？

谢谢!

编辑:嗨，只是让你知道代码:sum((node.sons.values() for node in current_nodes), [])虽然 pythonic，并没有真正快得多——如果节点列表很长(>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))

应该会更快。 lambda 上的 map 和 reduce 很慢。我不知道 chain 有多快；你可以试试

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

还有。