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

Question

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

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() 函数在处理列表连接时不如列表的扩展方法有效。

score 4 · Accepted Answer

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

应该更快。map而reduceon lambdas 很慢。我不知道有多快chain；你可以试试

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

也是。

1 回答 1