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)    

不过这样有个缺点，就是可能会因为哈希碰撞而丢失一些数据。对于我来说，1亿个哈希中出现1次碰撞也不是个大问题。

我试过md5哈希，但发现生成哈希的过程变成了瓶颈。

你有什么好的建议吗？

Answer 1

如果many_items已经在内存中，那你并不是在创建一个large_item的副本。你只是把它的引用存储在ignored集合里。

如果many_items是一个文件或者其他生成器，你就需要考虑其他的解决办法。

比如，如果many_items是一个文件，也许你可以存储文件中某个项目的指针，而不是存储实际的项目。

Answer 2

你需要决定哪个更重要：空间还是时间。

如果时间更重要，那你就需要为你的 large_item 创建独特的表示方式，这种方式要尽量占用少的空间（可能是一些 str 值），而且计算起来要快，不会出现重复的情况，然后把它们存储在一个 set 里。

如果空间更重要，那就找一个最快的磁盘存储解决方案，存储一个尽可能小的独特值来标识 large_item。

无论哪种情况，你都想要小而独特的标识符——根据 large_item 的特点，这可能会带来很大的好处，或者根本无法实现。

更新

它们是 HTML 内容的字符串

也许可以考虑一种混合解决方案：在内存中保持一个正常的 Python 哈希的 set，同时把实际的 HTML 内容存储在磁盘上，用那个哈希作为键；当你检查当前的 large_item 是否在 set 中并得到肯定的答案时，再用磁盘存储的方案进行二次确认，看看这是否是真正的匹配，然后根据情况跳过或处理。大概是这样的：

import dbf
on_disk = dbf.Table('/tmp/processed_items', 'hash N(17,0); value M')
index = on_disk.create_index(lambda rec: rec.hash)

fast_check = set()
def slow_check(hashed, item):
    matches = on_disk.search((hashed,))
    for record in matches:
        if item == record.value:
            return True
    return False

for large_item in many_items:
    hashed = hash(large_item) # only calculate once
    if hashed not in fast_check or not slow_check(hashed, large_item):
        on_disk.append((hashed, large_item))
        fast_check.add(hashed)
        process(large_item)    

顺便说一下：dbf 是我写的一个模块，你可以在 PyPI 找到它。

Answer 3

我假设你是在对网页进行哈希处理。你需要处理的网页数量最多是550亿个（这个数字可能还漏掉了一些重复的网页）。

你希望碰撞的概率小于十亿分之一，这意味着我们需要一个哈希函数，它的碰撞数量接近于完全随机的情况[ˆ1]。为了达到这个目标，我们需要的哈希范围大小是(55*10ˆ9)*10ˆ9。换句话说，log2((55*10ˆ9)*10ˆ9) = 66位。

[ˆ1]: 这里的哈希可以被视为随机选择的，p(碰撞) = (已占用范围)/(总范围)

由于速度是一个问题，但没有真正的加密需求，我们可以使用一个大于66位的非加密哈希，它具有上面提到的良好碰撞分布特性。

看起来我们在寻找的是Murmur3哈希的128位版本。人们报告说，在64位机器上，Murmur3_128的速度比MD5快了超过12倍。你可以使用这个库来进行速度测试。还有一个相关的回答，它：

• 展示了python的str_hash的速度测试结果，而这个速度你已经在其他地方认为是可以接受的——不过python的hash是32位的哈希，这样你只能存储2ˆ32/(10ˆ9)（也就是只有4）个值，碰撞的概率也小于十亿分之一。
• 引发了一个python绑定库，你应该可以直接使用。

最后，我希望我能阐明一些推理，这样你就可以在需要时与其他不同大小的函数进行比较（例如，如果你提高碰撞容忍度，或者你的索引集合的大小小于整个互联网等等）。