檢查一個巨大的列表中的流項目

Question

這是我們正在努力解決的問題。 我們正在處理大量項目的巨大流數據。我們也有一個預定義的項目列表。我們需要檢查一個流中的每個項目是否屬於我預定義的非常大的列表（大約400萬項）。查找/檢查操作應儘可能高效

如果這裏的人可以幫助我指出論文/算法，我可以閱讀以正確的方式處理這個問題，那將是非常好的。

感謝，

Answer 1

您可能需要來解決

• 之前縮小一些假設將你的預定義列表適合在主內存中？
• 訪問模式是什麼樣子？大多數流式傳輸的項目是相同類型還是所有類型都可以同等表示？
• 您的物品很小（整數/短弦）？如果沒有，每個人是否有唯一的標識符？
• 預定義列表是靜態還是會改變？多頻繁？

一般來說，您會希望維護一個對象的散列表（或代表這些對象的唯一鍵），並查看每個對象，因爲它通過您的流進來。散列表提供了快速查找，如果您的數據集是靜態的，它們對於您描述的用例來說是理想的。但是，在其他解決方案可能表現更好的情況下，上述問題應該揭示是否是這種情況。

進一步的閱讀，我會爲你向Data Structures和Big-O符號的文章在維基百科上

編輯：我砍死在一起，這種快速程序來衡量蟒蛇哈希查找性能：

#!/usr/bin/python 

import random 
import string 
import time 

# return a random username, all lowercase, between n and m characters long 
def generate_username(min_length = 5, max_length = 10): 
    n = random.randint(min_length, max_length) 
    return ''.join(random.sample(string.ascii_lowercase, n)) 

# Build a hash table of 4mil usernames (the 'predefined items') 
users = set() 
for i in xrange(4000000): 
    users.add(generate_username()) 

# Build a 'stream' of usernames to check against the hash table 
stream = [] 
for i in xrange(10000000): 
    stream.append(generate_username()) 

# Measure performance of hash lookups for 10mil usernames 
start = time.clock() 
for name in stream: 
    if name in users: 
     pass #print "%s is present" % name 
end = time.clock() 

print "%fs (%f - %f)" % (end - start, start, end) 

結果：

3.660000s (238.100000 - 241.760000) 

所以在Python中，你可以檢查10米在不到4秒的時間內，用戶數量達到上限，相當於流媒體大於17MB/s。你真的需要多快？ :)