过滤仅在非常大的列表中出现一次的项目

Question

我有一个很大的列表(超过1,000,000项),其中包含英文单词:

tokens = ["today", "good", "computer", "people", "good", ... ]

我想获得列表中只出现一次的所有项目

现在我正在使用:

tokens_once = set(word for word in set(tokens) if tokens.count(word) == 1)

但它确实很慢.我怎么能让这更快？

Answer 1

迭代一个列表,然后对每个元素再次执行,这使得它为O(N²).如果你用counta 替换你Counter,你在列表上迭代一次,然后再次在唯一元素列表上迭代,这使得它在最坏的情况下为O(2N),即O(N).

from collections import Counter

tokens = ["today", "good", "computer", "people", "good"]
single_tokens = [k for k, v in Counter(tokens).iteritems() if v == 1 ]
# single_tokens == ['today', 'computer', 'people']