在 Python 中使用 set() 的内存有效方法

Question

我正在研究在Python中对大量字符串进行重复数据删除的问题，并使用sets.Set()来解决这个问题。输入是文本文件中的一组字符串，输出是删除了重复项的同一组字符串。

该脚本需要能够在主内存有限（大约 2GB）的机器上运行，问题是集合的大小变得太大，我的输入是一个 800mb 的文本文件。

我的部分代码：

for String in InputFile:
    StringSet.add(String)

return StringSet

有没有更有效的方法来解决这个问题？我考虑过布隆过滤器和 trie，但我更喜欢 Set() 的 O(1) 效率。

编辑：我已经从sets.Set()切换到set()，后者应该具有更高的内存效率，但仍然不够高效。

Answer 1

您可以使用两个文件机制，在读取一行时计算散列，而不是存储现有字符串以删除重复项，如果散列不在现有散列集中，则该行将被写入输出文件并添加散列到哈希集，因为您在任何时候只需要在内存中拥有哈希表和一行，这将提高内存效率，除非您的行小于哈希长度。您还应该发现它会快得多，因为即使比较 64 字节哈希条目也比比较两行中的所有字符要快得多。

就像是：

import hashlib
hasher = hashlib.sha1 # You could use md5, SHA224, SHA256, SHA384 or SHA512
hashset = set() # You could also use a list here - speed V size would be interesting
with open(input_name, 'r') as infile:
    with open(output_name, 'w') as outfile:
        for line in infile.readlines():
            h = hasher(line).digest() # Hash the line
            if not h in hashset:
                outfile.write(line)
                hashset.add(h) # if using a list append(h)

唯一的问题是在大小和重复或冲突的机会之间平衡散列类型和长度。有关信息，摘要大小（以字节为单位）以及不同输入的相同值的声明机会为：

哈希字节安全声明
md5 16 1:2^64
sha1 20 1:2^80
沙224 28
sha256 32 1:2^128
沙384 48     
sha512 64 1:2^256