每个项目都是 17 个 32 位整数的数组。我可能可以为它们生成 120 位的唯一哈希值。
我有一个算法可以生成 9,731,643,264 个这些项目，并且想看看其中有多少是独一无二的。我推测其中最多 1/36 将是独一无二的，但不能确定。
在这种规模下，我真的无法在内存中执行此操作（因为我只有 4 个演出），所以我需要一种方法来保存这些列表，进行成员资格测试，并添加每个新的，如果它不存在的话。
我在 Linux 上使用 C(gcc) 工作，所以如果该解决方案可以从那里工作，那就太好了。
有任何想法吗？
这让我想起了很多年前我在解决“骑士之旅”时遇到的一些问题。（一个数学问题现在已经解决了，但不是我自己解决的。）
甚至您的哈希也没有太大帮助。. . 在几乎一个 GUID 的大小上，它们很容易在所有已知的宇宙中都是独一无二的。
将列表保存在磁盘上大约需要 0.75 太字节。. . 不管有没有 4 Gigs 的内存，你仍然需要一个巨大的磁盘来保存它们。你需要双倍或更多的磁盘来执行我在下面讨论的排序/合并解决方案。
如果您可以对该列表进行排序，那么您可以一次将列表扔到一个项目中，以寻找彼此相邻的唯一副本。当然，对这么多数据进行排序需要自定义排序例程（您编写的），因为它是二进制的（转换为十六进制会使您的数据大小加倍，但允许您使用标准例程）。. . 尽管可能即使在那里，他们也可能会因那么多数据而窒息。. . 所以你又回到了你自己的自定义例程。
需要考虑的一些事情：
对这么多数据进行排序将需要数周、数月甚至数年的时间。虽然您可以在内存中进行良好的堆排序或其他任何操作，但因为您只有这么多的磁盘空间，所以无论您在内存中做什么，您都可能会对文件进行“冒泡”排序。
根据您的生成算法的样子，您可以生成“一个内存负载”的数据，对其进行排序，然后将其写入磁盘中的文件（排序）。一旦完成，您只需“合并”所有这些单独的排序文件，这是一项更容易的任务（即使会有 1000 多个文件，它仍然是一个相对容易的任务）。
如果您的生成器可以告诉您有关您的数据的任何信息，请利用它来发挥您的优势。例如在我的情况下，当我处理 Knight's Moves 时，我知道我的输出值不断变大（因为我总是每一步添加一个位），这些小知识让我能够以一些独特的方式优化我的排序。查看您的数据，看看您是否知道类似的信息。
当然，使数据更小总是好的。例如，您谈论 120 哈希，但它是可逆的吗？如果是这样，请对哈希进行排序，因为它更小。如果没有，散列可能没有太大帮助（至少对于我的排序解决方案）。
我对此类问题的机制很感兴趣，我很乐意就这个主题交换电子邮件，只是为了讨论想法和可能的解决方案。
如果您可以对输入数据设置一些限制，您可能会让您的生活变得更轻松：即使假设只有 120 个有效位，大量重复值也表明分布不均匀，因为均匀分布会使给定样本不太可能出现重复大小10^10：
2^120 = (2^10)^12 > (10^3)^12 = 10^36 >> 10^10
如果您有连续的集群（而不是稀疏但重复的值），则可以通过对范围而不是原子值进行操作来获得很多收益。
我会做什么：
然后，您需要合并各个文件，这可以在线完成 - 即当文件变得可用时 - 与基于堆栈的合并排序操作方式相同：为每个文件关联一个等于文件中范围数的计数器并推送堆栈上的每个新文件。当堆栈顶部的文件的计数器大于或等于前一个文件时，将文件合并到一个新文件中，其计数器是合并文件中的范围数。