python - 查找两个非常大的列表之间的差异

Question

我有两个非常大的列表，一个长 331991 个元素，我们称它为 a，另一个长 99171 个元素，称它为 b。我想比较 a 和 b，然后返回 a 中不在 b 中的元素列表。这也需要尽可能高效，并且按照它们出现的顺序，这可能是给定的，但我想我也可以把它放在那里。

Answer 1

可以在 O(m + n) 时间内完成，其中 m 和 n 对应于两个列表的长度:

exclude = set(b)  # O(m)

new_list = [x for x in a if x not in exclude]  # O(n)

这里的关键是集有恒定时间的包含测试。或许您可以考虑让 b 成为一个集合。

另请参阅:List Comprehension

---

使用 your example :

>>> a = ['a','b','c','d','e']
>>> b = ['a','b','c','f','g']
>>> 
>>> exclude = set(b)
>>> new_list = [x for x in a if x not in exclude]
>>> 
>>> new_list
['d', 'e']