Python执行时间优化：河流排放树路径列表全连通扩展方法咨询

首先明确问题：我们有一个表示河流排放树的字符串，格式为From;To的边集合，原始内容是：

From;To 1;2 2;3 5;4 3;4 4;-999 9;6 6;5 10;7 8;7 7;5

需要生成所有自上而下的连通路径（包括直接和间接连通的，比如1;3、1;4、8;4这类），同时要尽可能优化代码的执行效率。

核心思路：用记忆化遍历避免重复计算 #

直接对每个节点做深度优先搜索（DFS）会产生大量重复遍历（比如多个父节点指向同一个子节点时，该子节点的后代会被多次计算）。最优方案是先构建树的邻接表，再用**记忆化（缓存）**存储每个节点能到达的所有后代节点，每个节点仅计算一次，后续直接复用缓存结果。

具体实现步骤&优化代码 #

from functools import lru_cache

def generate_all_river_paths(raw_data):
    # 1. 解析原始数据，构建邻接表（父节点到直接子节点的映射）
    edges = raw_data.split()
    adjacency = {}
    # 跳过表头"From;To"，处理每条边
    for edge in edges[1:]:
        from_node, to_node = edge.split(';')
        from_node = int(from_node)
        to_node = int(to_node)
        if to_node == -999:
            continue  # 终止节点无后续子节点，直接跳过
        if from_node not in adjacency:
            adjacency[from_node] = []
        adjacency[from_node].append(to_node)
    
    # 2. 记忆化函数：获取节点的所有后代（含间接连通的）
    @lru_cache(maxsize=None)
    def get_all_descendants(node):
        descendants = set()
        if node in adjacency:
            # 先添加直接子节点
            for child in adjacency[node]:
                descendants.add(child)
                # 递归添加子节点的所有后代
                descendants.update(get_all_descendants(child))
        return descendants
    
    # 3. 生成所有路径，用集合自动去重（效率远高于列表）
    all_paths = set()
    # 先加入原始的直接路径（排除指向终止节点的边）
    for edge in edges[1:]:
        if '-999' not in edge:
            all_paths.add(edge)
    # 加入所有间接连通的路径
    for from_node in adjacency:
        for to_node in get_all_descendants(from_node):
            all_paths.add(f"{from_node};{to_node}")
    
    return sorted(all_paths)

# 测试调用
raw_input = "From;To 1;2 2;3 5;4 3;4 4;-999 9;6 6;5 10;7 8;7 7;5"
result = generate_all_river_paths(raw_input)
print(result)

为什么这个方法效率高？ #

• 邻接表构建：O(n)时间复杂度（n为原始边数），快速建立节点间的直接关联。
• 记忆化DFS：每个节点仅被遍历一次，时间复杂度为O(V+E)（V为节点数，E为边数），彻底避免了重复递归的开销。
• 集合去重：用集合存储路径，添加和判断存在性的时间复杂度均为O(1)，比用列表做去重的O(n)效率提升显著。

额外优化建议 #

如果节点数量极大，手动用字典存储缓存结果（替代lru_cache）也是可行的，效果一致；若不需要结果排序，最后可直接返回列表形式的集合，省去排序的时间开销。

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