8

在2.6节和问题2中，原来的问题是这样的：

“给定一个包含 4,300,000,000 个 32 位整数的顺序文件，你如何找到至少出现两次的文件？”

我对这个练习的问题是：上述问题的技巧是什么，这个问题属于哪种一般算法类别？

4

4 回答 4

10

创建一个长度为 2^32 位（初始化为零）的位数组，大约为 512MB，适合任何现代机器的 RAM。

开始读取文件，int by int，检查与 int 的值具有相同索引的位，如果设置了该位，则发现重复，如果为零，则设置为 1 并继续文件中的下一个 int .

诀窍是找到合适的数据结构和算法。在这种情况下，所有内容都适合具有合适数据结构的 RAM，并且可以使用简单有效的算法。
如果数字是 int64，您需要找到合适的排序策略或进行多次传递，具体取决于您有多少额外的可用存储空间。

于 2011-04-02T07:06:14.007 回答
7

鸽笼原则——如果你在 M 个鸽笼中有 N 只鸽子，并且 N>M，那么一个洞里至少有 2 只鸽子。这组 32 位整数是我们的 2^32 个鸽笼，我们文件中的 43 亿个数字是鸽子。由于 4.3x10^9 > 2^32，我们知道有重复。

您可以应用此原则来测试我们正在寻找的副本是否在数字的子集中，代价是读取整个文件，而不是一次加载超过一点到 RAM 中——只需计算次数您会在测试范围内看到一个数字，并与该范围内的整数总数进行比较。例如，要检查 1,000,000 到 2,000,000（含）之间的重复项：

int pigeons = 0;
int pigeonholes = 2000000 - 1000000 + 1; // include both fenceposts
for (each number N in file) {
  if ( N >= 1000000 && N <= 2000000 ) {
    pigeons++
  }
}
if (pigeons > pigeonholes) {
  // one of the duplicates is between 1,000,000 and 2,000,000
  // try again with a narrower range
}

选择要检查的范围有多大与要读取 16GB 数据的次数取决于您：)

就一般算法类别而言，这是一个组合学（关于计数的数学）问题。

于 2011-04-03T11:41:57.557 回答
-1

对整数进行排序并循环遍历它们以查看连续整数是否重复。如果您想在内存中执行此操作，则需要 16GB 内存，这在当今的机器上是可能的。如果这是不可能的，您可以使用 mergesort 对数字进行排序并将中间数组存储到磁盘。

我的第一个实现尝试是使用来自 unix 的命令sort。uniq

于 2011-04-02T15:30:51.237 回答
-1

如果你的意思是 32 位正整数，我认为这个问题不需要一些特殊的算法或技巧来解决。只需一个简单的观察即可得出预期的解决方案。

我的观察是这样的，顺序文件将只包含 32 位整数（从 0 到 2 ^ 31 - 1）。假设您将所有这些都唯一地放在该文件中，您最终将得到 2 ^ 31 行。你可以看到，如果你把这些正整数再放一次，你最终会得到 2 ^ 31 * 2 行，它小于 4,300,000,000。

因此，答案是从 0 到 2 ^ 31 - 1 的整个正整数。

于 2011-04-02T07:11:27.013 回答