Python：如何快速从大列表a中删除列表b包含的元素？

原代码速度慢的核心原因是：列表的in查找和remove操作都是线性时间复杂度(O(n))，对于a这种百万级别的大列表，循环执行3万多次(b的长度)的线性操作，整体时间复杂度会达到O(len(b)*len(a))，效率极低。

下面给出几种高效的优化方案：

1. 利用集合差集（最快，无需保持原顺序） #

集合的查找、差集操作都是常数时间复杂度(O(1))，直接将a和b转为集合后做差集，再按需转回列表：

import itertools

# 直接生成集合，跳过列表转换的内存开销
a_set = set(itertools.product("12X", repeat=15))
b_set = set(itertools.product("1X", repeat=15))

# 执行差集操作，直接从a中移除所有b的元素
a_set -= b_set

# 如果需要列表类型，再转换
a = list(a_set)

2. 列表推导式+集合查找（需要保持原顺序） #

如果需要保留原a中元素的顺序，先把b转为集合，再通过列表推导式过滤a：

import itertools

a = list(itertools.product("12X", repeat=15))
# 将b转为集合，后续查找都是O(1)
b_set = set(itertools.product("1X", repeat=15))

# 过滤掉a中属于b的元素，生成新列表
a = [item for item in a if item not in b_set]

3. 直接过滤（最优，无需生成b） #

观察到b的元素是仅由1和X组成的15位元组，本质上是a中**不含字符'2'**的子集。因此可以直接在生成a的过程中过滤掉这些元素，连b都不需要生成：

import itertools

# 生成a时直接跳过不含'2'的元素
a = [item for item in itertools.product("12X", repeat=15) if '2' in item]

# 如果不需要立即占用大量内存，可用生成器表达式
# a = (item for item in itertools.product("12X", repeat=15) if '2' in item)

各方案对比 #

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