找到两个非常大的列表之间的差异

Question

我有两个非常大的列表,一个是331991个元素长,我们称之为一个,另一个是99171个元素长,称之为b.我想比较a到b然后返回一个不在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成为一个开始的集合.

另请参见:列表理解

使用你的例子:

>>> 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']