如何篩選出兩個巨大列表的列表項？

Question

我有一個巨大的列表，這是all_entries（目前80k整數項）。在此列表中包含我已在我的整個程序中處理的項目。

當我的程序使用以下方法時，通常需要大約30秒才能到達return語句。我如何加快速度？提示：new_entries是40k長，如此巨大。

def get_fresh_entries(self, new_entries, all_entries): 
    """ 
    :param new_entries: Entries from which some might already be in all_entries. 
    :param all_entries: Entries already handled and saved. 
    """ 
    fresh = [] 
    shuffle(new_entries) 

    for i in new_entries: 
     if i not in all_entries: 
      fresh.append(i) 
     if len(fresh) > 80000: 
      break 
    return fresh 

Answer 1

的唯一問題是，這是每一個新條目，並針對測試高達80K現有條目執行的行if i not in all_entries:加快進程。

在這裏，理解在列表或集合上執行測試時的差異非常重要。

• 測試一個元素是否在列表中就像測試某人是否在家時不知道地址（只是城鎮）並挨家挨戶一樣。
• 測試如果一個元素是一組像測試，如果有人在家，知道確切的地址和環單門鈴

所以，簡單地轉換all_entries一組一次（！）將消除主速度問題。

... 
all_entries_set = set(all_entries) 
for i in new_entries: 
    if i not in all_entries_set: 
     ... 

雖然還有其他提示如何使用set來加速程序是至關重要的，因爲它可以降低複雜性。

Answer 2

列表解析會做：

由於@Delgan評論，是更好，如果all_entries是一組。

all_entries = set(all_entries) 

然後：

fresh = [x for x in new_entries if x not in all_entries] 

而且看看itertools.ifilter，它是lazyly evaluated：

fresh = itertools.ifilter(lambda x: x not in all_entries, new_entries) 

如果你只需要保留第一n數據，因爲itertools是懶惰你可以這樣拿他們：

fresh = itertools.islice(itertools.ifilter(lambda x: x not in all_entries, 
              new_entries), 
         n)) 

或與列表理解一樣，但使用發電機來代替：

fresh = itertools.islice((x for x in new_entries if x not in all_entries), n) 

Answer 3

使用set操作可以顯著加快你的代碼。我定義了一個使用set操作的新函數get_fresh_entries_2。最後我添加了一個小的速度比較。利用組操作由一個巨大的因素

from random import shuffle 
from itertools import compress 
from time import time 

def get_fresh_entries_2(new_entries, all_entries): 
    shuffle(new_entries) 
    diff = set(new_entries)- set(all_entries) 
    if len(new_entries) > 80000: 
     ind = [i in diff for i in new_entries[:80000]] 
    else: 
     ind = [i in diff for i in new_entries] 
    fresh = compress(new_entries,ind) 
    return list(fresh) 


def get_fresh_entries(new_entries, all_entries): 
    """ 
    :param new_entries: Entries from which some might already be in all_entries. 
    :param all_entries: Entries already handled and saved. 
    """ 
    fresh = [] 
    shuffle(new_entries) 

    for i in new_entries: 
     if i not in all_entries: 
      fresh.append(i) 
     if len(fresh) > 80000: 
      break 
    return fresh 

new_entries = np.asarray(np.random.randint(1,11, size = (40000))).tolist() 
all_entries = np.asarray(np.random.randint(0,10, size = (80000))).tolist() 
t0 = time() 
a = get_fresh_entries(new_entries, all_entries) 
t1 = time() 
b = get_fresh_entries_2(new_entries, all_entries) 
t2 = time() 

t1-t0 # 4.321316957473755 sec 
t2-t1 # 0.005052804946899414 sec