mục Lọc mà chỉ xảy ra một lần trong một danh sách rất lớn

Question

Tôi có một danh sách lớn (hơn 1.000.000 bài), trong đó có chứa các từ tiếng Anh:

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

Tôi muốn có được tất cả các mục mà chỉ xảy ra một lần trong danh sách

bây giờ tôi đang sử dụng:

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

nhưng nó thực sự chậm. làm thế nào tôi có thể làm cho điều này nhanh hơn?

Answer 1

Bạn lặp qua danh sách và sau đó cho từng phần tử bạn làm lại, điều này làm cho nó trở thành O (N²). Nếu bạn thay thế count của mình bằng một số Counter, bạn lặp lại một lần trong danh sách và sau đó một lần nữa trong danh sách các phần tử duy nhất, trong trường hợp xấu nhất là O (2N), tức là 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']