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
相关产品推荐
相关产品推荐

