Python两个字典列表按键值匹配关联查询的代码优化方法

现有代码的问题 #

• 时间复杂度为 O(n*m)（n是输入列表长度，m是参考列表长度），数据量较大时性能损耗非常明显
• 每次匹配都需要重复生成参考字典的匹配键键值对，存在冗余计算

优化方案 #

核心思路是预先将参考列表转换为哈希查找表，将匹配键组成的不可变元组作为索引键，需要拷贝的键值对作为值，后续每个输入字典的匹配操作只需O(1)时间即可完成查找，整体时间复杂度降到 O(n+m)。

优化后代码 #

def lookup_dict(input_list, ref_list, matching_cols, copy_over_cols, copy_input_dict=False):
    # 第一步：预处理参考列表生成查找表
    ref_lookup = {}
    for ref_dict in ref_list:
        # 用匹配键的元组作为哈希表的key（元组可哈希可以作为字典key）
        match_key = tuple(ref_dict[col] for col in matching_cols)
        # 提取需要拷贝的键值对，如果要和原逻辑一致（重复匹配键取第一个），此处加if match_key not in ref_lookup判断
        copy_values = {col: ref_dict[col] for col in copy_over_cols}
        ref_lookup[match_key] = copy_values
    
    output_list = []
    reject_list = []
    for input_dict in input_list:
        current_key = tuple(input_dict[col] for col in matching_cols)
        if current_key in ref_lookup:
            # 如果需要避免修改原输入字典，可以先做拷贝
            target_dict = input_dict.copy() if copy_input_dict else input_dict
            target_dict.update(ref_lookup[current_key])
            output_list.append(target_dict)
        else:
            reject_list.append(input_dict)
    return output_list, reject_list

优化点说明 #

• 新增可选参数copy_input_dict：默认直接修改原输入字典和原逻辑保持一致，如果开启会拷贝输入字典再修改，避免污染原始输入数据
• 用推导式替代原来的tuple+dict嵌套写法，代码更简洁易读
• 省去了多余的matched标记变量，直接通过键是否在查找表中判断匹配结果
• 如果需要兼容匹配键不存在的场景，可以把[col]替换为.get(col, 你需要的默认值)避免抛出KeyError

功能验证 #

和示例参数运行后得到的结果完全符合预期：

input_list =  [{'a':1, 'b': 2, 'c':3},
               {'a':4, 'b': 5, 'c':6},
               {'a':7, 'b': 8, 'c':9}]
ref_list =    [{'a':1, 'b': 2, 'd':3, 'e': 10},
               {'a':4, 'b': 5, 'd':6, 'e': 11}]
matching_cols = ['a','b']
copy_over_cols = ['d','e']
output_list, reject_list = lookup_dict(input_list,ref_list,matching_cols,copy_over_cols)
print(output_list)
# 输出：[{'a': 1, 'b': 2, 'c': 3, 'd': 3, 'e': 10}, {'a': 4, 'b': 5, 'c': 6, 'd': 6, 'e': 11}]
print(reject_list)
# 输出：[{'a':7, 'b': 8, 'c':9}]

内容的提问来源于stack exchange，提问作者RH-NewDeveloper