这是我们试图解决的问题。我们正在处理大量项目的大量流数据。我们还有一个预定义的项目列表。我们需要检查流中的每个项目是否属于我的预定义列表,该列表非常庞大(大约 400 万个项目)。查找/检查操作应尽可能高效
如果这里的人们可以帮助我指出我可以阅读的论文/算法以正确的方式解决这个问题,那就太好了。
谢谢,
这是我们试图解决的问题。我们正在处理大量项目的大量流数据。我们还有一个预定义的项目列表。我们需要检查流中的每个项目是否属于我的预定义列表,该列表非常庞大(大约 400 万个项目)。查找/检查操作应尽可能高效
如果这里的人们可以帮助我指出我可以阅读的论文/算法以正确的方式解决这个问题,那就太好了。
谢谢,
在找到解决方案之前,您可能希望缩小一些假设范围
一般来说,您需要维护对象的哈希表(或表示这些对象的唯一键)并在每个对象通过您的流进入时查找它。哈希表提供快速查找,如果您的数据集是静态的,它们非常适合您描述的用例。但是,在某些情况下,其他解决方案可能会表现得更好,上述问题应该揭示是否是这种情况。
为了进一步阅读,我将向您介绍 Wikipedia 上的Data Structures和Big-O notation 文章
编辑:我编写了这个快速程序来测量 python 中的哈希查找性能:
#!/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 中,您可以在 4 秒内检查 1000 万个用户名,相当于流式传输 >17MB/s。你真的需要多快?:)