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从一开始就成为一个集合。

另请参阅：列表理解

---

使用您的示例：

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

Answer 2

让我们假设：

book = ["once", "upon", "time", ...., "end", "of", "very", "long", "story"]
dct = ["alfa", "anaconda", .., "zeta-jones"]

并且您想从书单中删除 dct 中存在的所有项目。

快速解决方案：

short_story = [word in book if word not in dct]

加快 dct 中的搜索：将 dct 转换为 set - 这具有更快的查找速度：

dct = set(dct)
short_story = [word in book if word not in dct]

万一这本书很长，记不住，你可以一个字一个字地处理。为此，我们可以使用生成器：

def story_words(fname):
"""fname is name of text file with a story"""
  with open(fname) as f:
    for line in f:
      for word in line.split()
        yield word

#print out shortened story
for word in story_words("alibaba.txt"):
  if word not in dct:
    print word

如果您的字典太大，您将不得不放弃速度并迭代字典的内容。但是这个我现在跳过。

Answer 3

这是转换b为集合的一种方法，然后从中过滤a不存在​​的元素：

from itertools import ifilterfalse

a = ['a','b','c','d','e']
b = ['a','b','c']
c = list(ifilterfalse(set(b).__contains__, a))
# ['d', 'e']