如何最小化Python中万级字典列表双层匹配循环的执行时间

原实现的性能根因 #

当前双层嵌套循环的时间复杂度为O(n*m)，对应19000条fielding记录、17000条player记录的规模，单次执行需要完成近3.23亿次id相等判断，无意义的重复全量遍历是耗时过高的核心原因。

优化实现思路 #

借助Python集合哈希查找平均O(1)的时间复杂度，将两次嵌套遍历替换为两次独立的单次遍历，整体时间复杂度可降低至O(n+m)，运行效率会实现两个数量级左右的提升。

优化后代码（保持原方案原地修改字典的行为） #

# 单次遍历fielding列表，提取所有id存入集合
fielding_valid_ids = {entry['id'] for entry in fielding}
# 单次遍历player列表，命中id集合的记录直接更新name字段
for entry in player:
    if entry['id'] in fielding_valid_ids:
        entry['name'] = 'Luke'

行为说明 #

• 上述代码和原逻辑的最终执行效果完全一致：遍历到所有同时存在于fielding和player列表中的相同id记录时，将player对应记录的name字段原地修改为Luke
• 即使fielding列表中存在重复的id记录，集合存储会自动去重，不会造成player字段的无意义重复赋值
• 因为集合的查找性能远高于列表的线性遍历，万级数据规模下，优化后的代码运行耗时会从原方案的数十秒级降到毫秒级，性能提升明显

可选写法（重新生成列表的场景） #

如果业务场景允许直接替换原player列表而非原地修改字典，可以用推导式简化代码，性能和上述实现完全一致：

fielding_valid_ids = {entry['id'] for entry in fielding}
player = [
    {**entry, 'name': 'Luke'} if entry['id'] in fielding_valid_ids else entry
    for entry in player
]

注意：该写法会生成全新的字典与列表，若其他代码引用了原player列表中的旧字典对象，会无法感知字段更新，需要按实际业务依赖关系选择实现方式 #

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