python - 存储数百万数组的有效方法，并执行 IN 检查

Question

大约有 300 万个数组 - 或 Python 列表\元组(并不重要)。每个数组由以下元素组成:

['string1', 'string2', 'string3', ...]  # totally, 10000 elements

这些数组应该存储在某种键值存储中。为了简单的解释，我们现在假设它是 Python 的字典。

所以，300 万个键，每个键代表一个 10000 个元素的数组。

Lists\tuples 或任何其他自定义的东西 - 这并不重要。重要的是数组应该包含字符串——utf8 或 unicode 字符串，每个字符串 5 到大约 50 个字符。还有大约 300 万个可能的字符串。如果确实需要，可以用整数替换它们，但为了更高效的进一步操作，我更愿意使用字符串。

虽然很难为您提供数据的完整描述(它既复杂又奇怪)，但它类似于同义词 - 假设我们有 300 万个单词 - 作为字典键 - 每个单词都有 10k 个同义词- 或列表的元素。

像那样(不是真正的同义词，但它会给你想法):

{
    'computer': ['pc', 'mac', 'laptop', ...],  # (10k totally)
    'house': ['building', 'hut', 'inn', ...],  # (another 10k)
     ...
}

元素 - '同义词' - 如果需要可以排序。

稍后，在填充数组后，有一个循环:我们遍历所有键并检查其值中是否有某些变量。例如，用户输入单词“computer”和“laptop”——如果“laptop”是“computer”的同义词，我们必须快速回复。这里的问题是我们必须检查它数百万次，大概 2000 万次左右。试想一下，我们很多用户输入了一些随机词——“计算机”和“汽车”、“电话”和“建筑物”等等。它们可能“匹配”，也可能不匹配'匹配'。

所以，简而言之 - 我需要的是:

• 高效地存储这些数据结构，
• 能够快速检查某个项目是否在数组中。

我应该能够将内存使用量保持在 30GB 以下。此外，我应该能够在 Xeon CPU 上在不到 10 小时的时间内完成所有迭代。

有大约 0.1% 的错误答案(正面和负面)是可以接受的，但最好减少它们或根本没有它们。

这里最好的方法是什么？算法、代码链接，任何东西都非常受欢迎。另外 - 我的一个 friend 建议在这里使用布隆过滤器或玛丽莎尝试 - 他是对的吗？我没有和他们一起工作。

Answer 1

我会将每个唯一字符串映射到一个数字 ID，然后关联一个 bloom filter对于 <0.1% 的错误率，每个元素大约 20 位。 20 位 * 10000 个元素 * 300 万个键是 75GB，所以如果你的空间有限，那么在内存中存储一​​个更小的不太准确的过滤器，并在磁盘上存储更准确的过滤器，如果第一个过滤器说它可能是匹配的，它会被调用。

有alternatives , 但它们只会将尺寸从 1.44·n·ln₂(1/ε) 减小到 n·ln₂(1/< i>ε) 每个 key ，在您的情况下 ε=0.001 因此理论上的限制是每个 key 99658 位的数据结构，或每个元素 10 位，即 298,974,000,000 位或38 GB。

因此 30GB 低于具有您所需的性能和条目数的数据结构的理论限制，但在球场内。