Python深度优先搜索层级遍历父子节点 慢for循环优化咨询

你这段循环耗时过高的核心原因是当前遍历逻辑的时间复杂度为O(n²)，链式层级结构下每个父节点都要重复遍历所有后代做层级加一操作，同时存在多处无意义的语法开销，此前尝试的多线程受Python GIL限制对CPU密集型循环无效，LRU缓存因入参节点重复率低命中率几乎为0，自然没有效果。可按以下优先级优化：

1. 优先消除语法层面的冗余开销（可立即提效2~3倍） #

原代码存在多处不必要的耗时操作，直接修改即可见效：

• 去掉多余的.keys()调用：Python字典的in操作默认校验key，if c in graph.visited_nodes.keys()会额外生成一次字典key视图，直接写成if c in graph.visited_nodes即可
• 去掉多余的list(d)转换：d本身就是可直接解包的元组，list(d)属于无意义的类型转换开销
• 用列表推导+extend替换逐次append：列表推导的执行效率远高于循环内逐次append，子节点的后代可直接批量合并

修改后的代码如下：

descendants = []
current_node = n_stack.last
for c in graph.nodes_dict[current_node]:
    if c not in graph.visited_nodes:
        continue
    # 直接解包元组+列表推导批量生成后代
    descendants.extend([(dc, ip, ic, lv + 1) for dc, ip, ic, lv in graph.visited_nodes[c] if lv != -1])

2. 调整存储结构消除内层循环（可提效1~2个数量级） #

你现在visited_nodes每个节点存储全量后代元组，每次计算父节点后代都要遍历所有子节点的后代做层级+1，属于完全可以避免的重复计算：

• 新增node_level字典单独存储每个节点自身的层级，后代的层级直接通过「父节点层级 + 子节点自身层级」计算，不需要每个后代元组都存层级
• 每个节点的visited_nodes只存非循环后代的ID列表，不需要存完整的元组，父节点处理时直接复用子节点的后代列表即可，无需遍历每个元素修改

调整后这段循环的内层遍历可以完全删除，耗时直接从O(k)（k为子节点后代数）降到O(1)。

3. 调整遍历逻辑从根源降低时间复杂度（适用于节点量>1万的场景） #

你当前的DFS栈遍历逻辑本质是重复计算每个节点的后代集合，对于你给出的链式层级结构来说时间复杂度是O(n²)，1万节点就会产生近5000万次无效操作：

• 先对排除循环后的图做拓扑排序，按拓扑序从根节点开始依次计算每个节点的层级和后代，每个节点仅需处理1次，整体时间复杂度降到O(n)
• 如果必须保留现有栈遍历逻辑，可新增缓存存每个节点已经计算好的后代集合，不同父节点用到同一个子节点的后代时直接复用，不用重复生成。

4. 极端场景优化 #

如果节点量超过10万，可引入numba的@njit装饰器编译核心循环逻辑，绕过Python解释器的执行开销，执行效率可再提升10~50倍，注意要将用到的字典、列表替换为numba支持的原生类型即可。

内容的提问来源于stack exchange，提问作者Maa