python - 过滤在一个非常大的列表中只出现一次的项目

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²)。如果你用 a 替换你count的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']