Python中如何高效计算两个嵌套列表的差集

核心思路 #

Python 中的列表属于不可哈希类型，无法直接存入集合做 O(1) 复杂度的成员查询，因此我们可以先把 B 中的所有子列表转为可哈希的元组存入集合，再遍历 A 筛选不在集合中的元素即可。整体时间复杂度为 O(len(A)+len(B))，远优于双重 for 循环的 *O(len(A)len(B))，数据量越大性能优势越明显。

实现代码 #

A = [[1, 2, 3], [1, 2, 4], [4, 5, 6]]
B = [[1, 2, 3], [1, 2, 6], [4, 5, 6], [4, 3, 6]]

# 预处理B为元组集合，成员查询复杂度为O(1)
b_tuple_set = set(tuple(sub_list) for sub_list in B)
# 筛选A中不存在于B的子列表
a_minus_b = [sub_list for sub_list in A if tuple(sub_list) not in b_tuple_set]

print(a_minus_b) # 输出：[[1, 2, 4]]

适用说明 #

• 该方案默认子列表的元素顺序严格匹配才算同一个元素，完全符合题目的需求
• 如果子列表内部还嵌套了可变类型（如深层列表、字典），需要先递归将所有可变结构转为不可哈希类型（如元组、冰冻集合）后再使用该方法

内容的提问来源于stack exchange，提问作者K.N