提高性能：在只出現一次

Question

我有一個大名單（25000項，14000個字）這樣的（大）列表中刪除所有字符串：

之前（請看看下面的右邊的列表） ：

texts = ['Lorem hello ipsum', 'Lorem ipsum generator machine', ... 'hello Lorem ipsum'] 

我想刪除整個目錄只出現一次的所有單詞。

後：

texts = ['Lorem generator ipsum', 'Lorem ipsum generator machine', ..., 'Machine Lorem ipsum'] 

我現在已經這樣做，但它確實慢（約2小時）。

all_tokens = sum(texts, []) 
tokens_once = set(word for word in set(all_tokens) if all_tokens.count(word) == 1) 
texts = [[word for word in text if word not in tokens_once] for text in texts] 

如何提高性能？

---

編輯：

@DSM是正確的，我的輸入列表看起來像這樣。是我的錯，對不起：

texts = [['Lorem', 'hello', 'ipsum'], ['Lorem', 'ipsum', 'generator', 'machine'], ... ['hello, 'Lorem', 'ipsum']] 

Answer 1

您可以使用collections.Counter這裏存儲每個字的計數，然後篩選出在此基礎上計算字數。使用collection.Counter您可以獲得O(N)時間內的物品計數，而您當前的方法（list.count）需要O(N**2)時間。

和never use sum for flattening a list of lists，它非常慢（在你的實際代碼中你有字符串列表，並且sum()會引發錯誤）。我在我的答案中使用了嵌套列表理解，如果你實際上有列表的列表，那麼最好在這裏使用itertools.chain.from_iterable。

>>> from collections import Counter 
>>> texts = ['Lorem hello ipsum', 'Lorem ipsum generator machine', 'hello Lorem ipsum'] 
>>> c = Counter(word for x in texts for word in x.split()) 
>>> [' '.join(y for y in x.split() if c[y] > 1) for x in texts] 
['Lorem hello ipsum', 'Lorem ipsum', 'hello Lorem ipsum'] 

時機比較：

In [8]: texts = ['Lorem hello ipsum', 'Lorem ipsum generator machine', 'hello Lorem ipsum'] 

In [9]: huge_texts = [x.split()*100 for x in texts]*1000 #list of lists        

In [10]: %%timeit 
from collections import Counter 
from itertools import chain 
c = Counter(chain.from_iterable(huge_texts)) 
texts = [[word for word in x if c[word]>1] for x in huge_texts] 

1 loops, best of 3: 791 ms per loop 

In [11]: %%timeit 
all_tokens = sum(huge_texts, []) 
tokens_once = set(word for word in set(all_tokens) if all_tokens.count(word) == 1) 
texts = [[word for word in text if word not in tokens_once] for text in huge_texts]               

1 loops, best of 3: 20.4 s per loop 

Answer 2

緩慢的部分是在這裏：

`all_tokens.count(word) == 1` 

對於每一個字，你問的代碼遍歷整個列表計算當前單詞的項目數。即：

list1 = [1,2,3,1,5] 

所以，第一個單詞是1。要知道這個列表中有多少個1，我們必須檢查全部5個，看它們是否爲1.我們將返回2的計數 - 到目前爲止我們已經完成了5次比較。然後我們檢查2 - 必須與每個條目進行比較來計算有多少個是2，總數是1.

該計數器是正確的方法，只是想解釋更多的原因。

Answer 3

你的代碼和計數器都有很多隱藏的機器：我建議提出一個好的算法，然後再考慮一下Python。

讓我們來看看你的代碼：

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

在這裏，我們正在一組all_tokens。如果Python的set使用散列表，那麼您可以在O（N）時間內構建集合。如果Python的set使用某種二叉樹，則可以在O（N log N）時間內構建該集。

好的，所以你有N'獨特的元素。現在您計算每個元素在all_tokens中出現的次數。這意味着你正在做O（N * N'）工作，或簡稱O（N^2）。

這很糟糕。

我們該如何做得更好？

一種方法是對all_tokens進行排序。

現在我們知道重複元素必須在排序列表中彼此相鄰。因此，我們只需沿着列表行進，看看一個元素是否與之​​前的元素相同：如果是這樣，我們有一個副本。排序需要O（N log N）時間，然後查找重複項需要O（N）時間。將複製的元素複製到一個新的向量中需要O（1）分期時間，因此該算法在O（N log N）時間內運行，這非常好。

lorem="lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat sed diam voluptua at vero eos et accusam et justo duo dolores et ea rebum stet clita kasd gubergren no sea takimata sanctus est lorem ipsum dolor sit amet" 

的算法看起來像這樣：

lorem="lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat sed diam voluptua at vero eos et accusam et justo duo dolores et ea rebum stet clita kasd gubergren no sea takimata sanctus est lorem ipsum dolor sit amet" 

all_tokens=lorem.split() 

all_tokens.sort() 

duplicate_count=0 
more_than_once=[] 
for i in range(1,len(all_tokens)): 
    if all_tokens[i-1]==all_tokens[i]: 
    duplicate_count+=1 
    if duplicate_count==1: 
     more_than_once.append(all_tokens[i]) 
    else: 
    duplicate_count=0 

我們可以做得更好？是!

想象一下，我們有一個散列表，允許我們在O（1）時間插入/檢索一個元素。我們可以在O（N）時間內走下一個項目列表，並在每次看到該項目時在散列表中增加它們的條目。然後，我們可以在O（N）時間內檢索重複項目的列表。

這是什麼樣子？

hash_table={} 
for i in all_tokens: 
    if hash_table.has_key(i): 
    hash_table[i]+=1 
    else: 
    hash_table[i]=1 

more_than_once=[i for i in hash_table if hash_table[i]>=2] 

在Python的字典中沒有作爲一個哈希表它將被實現爲一種二叉搜索樹的這個代碼回落到作爲一個O（N日誌N）的算法實現的情況下。

當然，Python可以使用各種各樣的花式容器和庫來抽象這個過程，但是從深層次來說，這些都將會像我剛剛描述的那樣做很多事情。

就個人而言，在尋找能夠加速操作的特定於語言的功能之前，我更願意找到一種解決問題的好算法。