c - 在 C 中为成员资格测试保留一个大列表

Question

每一项都是一个由 17 个 32 位整数组成的数组。我大概可以为它们生成 120 位唯一的哈希值。

我有一个算法可以生成 9,731,643,264 个这些项目，并且想看看其中有多少是独一无二的。我推测其中最多 1/36 是独一无二的，但不能确定。

在这种规模下，我无法在内存中真正做到这一点(因为我只有 4 个演出)，所以我需要一种方法来保留这些列表，进行成员资格测试，并添加每个新的(如果还没有)。

我在 Linux 上使用 C(gcc) 工作，所以如果解决方案可以从那里工作，那就太好了。

有任何想法吗？

Answer 1

这让我想起了多年前我在解决“骑士之旅”的过程中遇到的一些问题。 (一个数学问题，现在已经解决了，但不是我解决的。)

甚至你的哈希也没有多大帮助。 . .在几乎一个 GUID 大小的情况下，它们很容易在所有已知的宇宙中都是独一无二的。

仅将列表保存在磁盘上大约需要 0.75 Terrabytes。 . .无论是否有 4 Gig 内存，您仍然需要一个巨大的磁盘来容纳它们。并且您需要两倍或更多的磁盘来执行我在下面讨论的排序/合并解决方案。

如果您可以对该列表进行排序，那么您可以一次将一个项目扔到列表中，以寻找彼此相邻的唯一副本。当然，对这么多数据进行排序需要自定义排序例程(您编写的)，因为它是二进制的(转换为十六进制会使数据大小加倍，但允许您使用标准例程)。 . .尽管可能即使在那里，他们也可能会因为这么多数据而窒息。 . .所以你又回到了你自己的自定义例程。

需要考虑的一些事情:

对这么多数据进行排序需要数周、数月甚至数年的时间。虽然您可以在内存中进行良好的堆排序或任何其他操作，但因为您只有这么多磁盘空间，所以无论您在内存中做什么，您都可能会对文件进行“冒泡”排序。

根据您的生成算法的样子，您可以生成“一个内存负载”的数据，将其排序，然后将其写入磁盘文件(已排序)。完成后，您只需要“合并”所有这些单独的排序文件，这是一项容易得多的任务(即使认为会有 1000 个文件，这仍然是一项相对容易的任务)。

如果您的生成器可以告诉您有关数据的任何信息，请充分利用它。例如，在我的情况下，当我处理骑士的移动时，我知道我的输出值不断变大(因为我每次移动总是增加一位)，这些小知识使我能够以一些独特的方式优化我的排序。看看你的数据，看看你是否知道类似的东西。

使数据更小当然总是好的。例如，您谈论的是 120 哈希值，但这是可逆的吗？如果是这样，请对哈希进行排序，因为它较小。如果没有，散列可能没有那么大的帮助(至少对于我的排序解决方案)。

我对此类问题的机制很感兴趣，我很乐意就这个主题交换电子邮件，只是为了讨论想法和可能的解决方案。