You need to enable JavaScript to run this app. Python DFS路径查找优化:解决三重for循环执行效率低下问题
优惠活动
大模型
产品
解决方案
定价
更多

Python DFS路径查找优化:解决三重for循环执行效率低下问题

原实现性能瓶颈

原find_path函数本质是匹配所有满足[A->B, A->C, C->B]结构的闭合三元路径,当前实现的问题在于:

  • 采用三重全量嵌套循环,在10000条数据的规模下,时间复杂度为O(n³),实际计算量达万亿级,完全不可用
  • 循环内反复对路径字符串做split("/")重复解析,且重复从原字典查找元数据,冗余开销极高
  • 无差别遍历所有路径做交叉比对,产生大量无意义的计算。
Pythonic优化实现

核心优化思路

完全匹配原逻辑输出,不生成多余排列,通过预解析+哈希索引将全量遍历替换为常数级查表,把时间复杂度压缩到接近线性:

  • 单次遍历原数据,完成所有路径的字符串解析,避免循环内重复split
  • 构建两类索引:
    • 以路径起点为键,收纳所有从该起点出发的路径条目,替代二重全量遍历
    • 以(起点, 终点)二元组为键,直接定位对应路径的元数据,替代第三重全量遍历
  • 仅在同起点的路径集合内做配对,无需跨集合的全量交叉比对。

优化后代码

from time import perf_counter
from typing import List, Generator, Dict


def find_path(data: Dict) -> Generator:
    # 单次遍历预构建索引
    start_edge_map: Dict[str, list] = {}
    edge_lookup: Dict[tuple, tuple] = {}
    for path_str, meta in data.items():
        src, dst = path_str.split("/")
        parsed_entry = ([src, dst], meta["amount"], meta["id"])
        # 索引所有同起点的路径
        start_edge_map.setdefault(src, []).append(parsed_entry)
        # 索引(起点,终点)对应的完整条目
        edge_lookup[(src, dst)] = parsed_entry

    # 遍历所有同起点路径集合匹配闭合环
    for _, edge_list in start_edge_map.items():
        for a_to_b in edge_list:
            target_end = a_to_b[0][1]
            for a_to_c in edge_list:
                c_node = a_to_c[0][1]
                # 完全匹配原逻辑中"pair2终点不等于pair1终点"的判断
                if c_node == target_end:
                    continue
                # 直接查表找C->B的闭合路径,无全量遍历
                c_to_b = edge_lookup.get((c_node, target_end))
                if c_to_b:
                    yield (*a_to_b, *a_to_c, *c_to_b)

一致性验证

对提供的测试用例,输出结果与原实现完全一致:

The path to traverse is: (['CD', 'TC'], 4, 6, ['CD', 'EH'], 7, 3, ['EH', 'TC'], 6, 4)
The path to traverse is: (['BT', 'TH'], 3, 7, ['BT', 'TX'], 2, 8, ['TX', 'TH'], 1, 9)

性能对比

  • 原实现时间复杂度O(n³),10000条数据下预估执行耗时数小时
  • 优化后时间复杂度O(n + k²),其中k为每个起点下的平均路径数(远小于总数据量),10000条数据下执行耗时可控制在毫秒级
  • 全程无多余排列生成,无重复字符串解析,符合Python中“用查表替代嵌套遍历”的通用优化原则。

内容的提问来源于stack exchange,提问作者Corfucinas

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.12 15:36:00