如何快速比较两个百万级规模的字典列表？

原代码运行极慢的核心原因是列表的in操作是线性查找：每次判断i not in list2都要遍历整个100万条的list2，100万次遍历的总操作量达到1e12级别，耗时自然爆炸。

最快的优化思路是把list2转换成哈希集合（查找时间复杂度O(1)），但字典本身不可哈希，需要先将字典转成可哈希的结构，同时保证内容相同的字典转换后结果完全一致。

优化实现代码 #

def compare_lists_fast(list1, list2):
    # 将list2的所有字典转为「排序后的键值对元组」，存入集合
    list2_set = {tuple(sorted(d.items())) for d in list2}
    # 遍历list1，转成同样结构后检查是否不在集合中
    return [d for d in list1 if tuple(sorted(d.items())) not in list2_set]

关键细节说明 #

• 为什么用sorted(d.items())：确保两个内容完全一致但键顺序不同的字典（比如{"a":1, "b":2}和{"b":2, "a":1}）转换后的元组完全相同，避免因键顺序差异导致的误判。
• 集合的性能优势：集合的成员检查是O(1)时间复杂度，整个算法的时间复杂度降到O(nk log k + mk log k)（k是单个字典的键数量，远小于百万），实际运行时间会从小时级压缩到秒/分钟级。
• 特殊情况处理：如果字典中包含不可哈希的值（比如列表、嵌套字典），需要先把这些值也转成可哈希结构（比如嵌套字典同样转成排序后的元组），否则无法存入集合。

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