关于文件检索索引的算法问题

Question

有一个问题，我也有解决办法。但我不明白解决办法。请帮助一些例子和淋浴一些经验。

问题

给定一个包含大约3亿个社会保险号码(9位数字)的文件，找到一个不在文件中的9位数字。您有无限的驱动器空间，但只有2MB的RAM可供您使用。

回答

在第一步中，我们构建一个初始化为0的数组2^16整数，对于文件中的每个数字，我们使用它的16个最重要的位来索引这个数组并增加这个数字。

由于文件中的数字小于2^32，因此数组中肯定有(至少)一个小于2^16的数字。这告诉我们，在具有这些上位的可能数字中至少有一个数字缺失。

在第二次测试中，我们只能关注与此标准匹配的数字，并使用大小为2^16的位向量来识别丢失的数字之一。

Answer 1

为了更简单的解释，假设你有一个两位数的列表，每个数字在0到3之间，但是你不能腾出16位去记住16个可能的数字中的每一个，不管你是否已经遇到过。您要做的是创建一个由4个3位整数组成的数组a，在a[i]中，使用第一个数字i存储多少个数字。(两位整数是不够的，因为您需要值0、4和它们之间的所有数字。)

如果你有文件

00，12，03，31，01，32，02

您的数组将如下所示：

4，1，0，2

现在您知道了，所有以0开头的数字都在文件中，但是对于其余的每一个数字，至少都缺少一个。让我们选择1。我们知道至少有一个以1开头的数字不在文件中。所以，创建一个4位的数组，每个数字从1开始，设置适当的位，最后，选择一个没有设置的位，在我们的示例中，如果可能是0。现在我们有了解决办法: 10。

在这种情况下，使用这种方法是12位和16位的区别。使用您的数字，这是32 kB和119 MB之间的区别。

Answer 2

总的来说，假设没有重复项，文件中可能存在的数字大约有1/3。

这样做的目的是让两次通过数据。将每个数字视为32位(无符号)数字.在第一次测试中，跟踪在最重要的16位中有多少个数字具有相同的数字。在实践中，会有一些代码存在于零(例如，10位SSN的所有代码；很可能，第一位数为零的所有代码也会丢失)。但是，在非零计数的范围中，大多数将不会有65536个条目，这就是如果范围内没有空白，会出现多少个条目。因此，稍微小心一点，您可以在第二次测试中选择一个要集中注意的范围。

如果幸运的话，您可以在100,000,000.999,999,999,999中找到一个零条目的范围--您可以选择该范围中的任何数字作为缺失。

假设您不太幸运，选择一个位数最少的位(或其中任何一个条目少于65536 )；将其称为目标范围。将数组重置为所有零。再读一遍数据。如果读取的数字不在目标范围内，请忽略它。如果它在此范围内，则通过将该数字的低阶16位数组值设置为1来记录该数字。读取完整个文件后，数组中任何一个零的数字都表示缺少SSN。