用于跟踪重复项的python数据类型

Question

我经常用这样的东西跟踪重复:

processed = set() 
for big_string in strings_generator:
    if big_string not in processed:
        processed.add(big_string)
        process(big_string)

我正在处理大量数据,因此不希望在内存中维护已处理的集合.我有一个使用sqlite将数据存储在磁盘上的版本,但是这个过程运行得慢得多.

要减少内存使用你对使用这样的哈希的看法:

processed = set() 
for big_string in string_generator:
    key = hash(big_string)
    if key not in ignored:
        processed.add(key)
        process(big_string)    

缺点是我可能会偶尔通过哈希冲突丢失数据.10亿次哈希中的1次碰撞对我来说不是问题.

我尝试了md5哈希,但发现生成哈希成了瓶颈.

你会建议什么呢？

Answer 1

我假设您正在对网页进行哈希处理。您最多必须对550 亿个网页进行哈希处理进行哈希处理（该方法几乎肯定会忽略一些重叠）。

\n\n

您愿意接受小于十亿分之一的碰撞机会，这意味着如果我们查看一个哈希函数，其碰撞次数接近于哈希真正随机时得到的碰撞次数[\xcb\x861]，我们想要一个大小为 的哈希范围(55*10\xcb\x869)*10\xcb\x869。那是log2((55*10\xcb\x869)*10\xcb\x869) = 66位。

\n\n

[\xcb\x861]：由于可以认为哈希是为此目的随机选择的，\n p(collision) = (occupied range)/(total range)

\n\n

由于存在速度问题，但没有真正的加密问题，我们可以使用 > 66 位非加密哈希，并具有上述良好的冲突分布属性。

\n\n

看起来我们正在寻找Murmur3哈希的 128 位版本。人们报告称，在 64 位计算机上，Murmur3_128 与 MD5 相比，速度提高了 12 倍以上。您可以使用该库进行速度测试。另请参阅此相关答案，其中：

\n\n

\n
• 显示 python\'s 范围内的速度测试结果，尽管 python\'s是一个 32 位哈希，但您在其他地方str_hash已经认为可以接受该速度\xe2\x80\x93hash2\xcb\x8632/(10\xcb\x869)只留下（只有 4 个）值存储碰撞的可能性不到十亿分之一。
\n
• 产生了一个python 绑定库，您应该能够直接使用它。
\n

\n\n

最后，我希望概述了一个推理，可以让您在需要时与不同大小的其他函数进行比较（例如，如果您提高了碰撞容错能力，如果索引集的大小小于整个互联网） ， ETC， ...）。

\n