检查一个巨大的列表中的流项目

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。你真的需要多快？ :)