如何加速两个大型列表间的字符串匹配？

原代码采用双重循环遍历两个列表，时间复杂度为O(n*m)，当两个列表各有数千个元素时，会产生数百万次循环操作，这是速度慢的核心原因。通过构建哈希表（字典）将查找操作的时间复杂度降至O(1)，可大幅提升匹配效率。

具体优化思路 #

1. 先遍历其中一个列表，将每个元素的匹配键作为字典的键，对应的文件路径作为值（若存在多个相同匹配键的元素，用列表存储所有路径）
2. 再遍历另一个列表，根据当前元素的匹配键直接在字典中查找对应路径，找到后写入结果文件

优化后的代码 #

import os
import glob

list1 = glob.glob("/data0/*.txt")
list2 = glob.glob("/data1/*.txt")

# 构建list2的匹配键到文件路径的映射字典
match_map = {}
for file_path in list2:
    basename = os.path.basename(file_path)
    parts = basename.split(".")
    match_key = f"{parts[0]}_{parts[3]}"
    # 处理同一匹配键对应多个文件的情况
    if match_key not in match_map:
        match_map[match_key] = []
    match_map[match_key].append(file_path)

with open("result.txt", "w") as fout:
    for file_path in list1:
        basename = os.path.basename(file_path)
        parts = basename.split(".")
        match_key = f"{parts[0]}_{parts[3]}"
        # 直接通过字典查找，时间复杂度O(1)
        if match_key in match_map:
            for matched_path in match_map[match_key]:
                fout.write(f"{file_path};{matched_path}\n")

额外优化细节 #

• 减少重复解析：每个文件路径只调用一次os.path.basename和split，避免重复计算
• 更高效的字符串拼接：使用f-string替代+拼接，既提升效率又增强可读性
• 兼容一对多场景：如果list2中有多个文件对应同一匹配键，字典会存储所有路径，确保不会遗漏匹配对

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