python - 计算大型列表的方法

Question

假设，我需要计算各种哈希方案的冲突。输入序列中的元素数为 1e10^8 或更多。不知道如何分析计算，所以使用蛮力。

显然不要将这个哈希列表保存在 RAM 中。这是为我的需要编写代码的最佳方式吗？我应该将它转储到数据库中还是什么？首选使用哪些库？

谢谢！

Answer 1

我建议保留一组文件，每个文件都以其中包含的哈希前缀命名（例如，如果您使用前缀长度为 6，那么命名的文件ffa23b.txt可能包含哈希ffa23b11d4334、 ...ffa23b712f3等）。每次读取散列时，都将其附加到文件中，其名称对应于散列的前 N ​​个字符。

您还可以使用布隆过滤器快速排除大部分哈希是唯一的，而无需将所有哈希存储在内存中。这样，如果对布隆过滤器的检查表明您之前可能确实见过它，那么您只需要回退到搜索给定的前缀文件——这种情况很少发生。

Answer 2

简短的回答：如果你有几 GB 的 RAM，请使用 Python 字典，这是最简单的实现方法（并且可能运行得更快）。你可以这样做：

>>> mydict = {}
>>> for i in some_iterator:
        mydict[i] = ''

然后检查映射中是否存在密钥：

>>> 0 in mydict
True

>>> 123456789 in mydict
False

长答案：您可以使用持久键值存储，例如GDBM（它看起来像 Berkeley DB）或其他类型的数据库——但这种方法比仅使用 Python 字典要慢得多；另一方面，通过这种方法，您将获得持久性（如果需要）。

您可以将 GDBM 理解为保存在单个文件中的字典（键值存储）。您可以按如下方式使用它：

>>> import gdbm
>>> kv = gdbm.open('my.db', 'cf')

然后my.db将创建该文件（请参阅Python GDBM 文档以了解其cf含义）。

但它有一些限制，因为只支持字符串作为键和值：

>>> kv[0] = 0
Traceback (most recent call last)
[...]
TypeError: gdbm mappings have string indices only

>>> kv['0'] = 0
Traceback (most recent call last)
[...]
TypeError: gdbm mappings have string elements only

>>> kv['0'] = '0'

您可以使用具有虚拟值的所有键填充 gdbm 数据库：

>>> for i in some_iterator:
        kv[str(i)] = ''

然后检查映射中是否存在密钥：

>>> '0' in kv
True

>>> '123456789' in kv
False