algorithm - 从硬盘中排序大量整数

Question

在内存为 2 GB 的硬盘上给定 100 GB 整数数据，如何以最少的磁盘操作对整数进行排序。这里从磁盘中取一个数字被认为是一次磁盘操作(尽管实际上可以取一个数据 block )。

我们可以使用磁盘上额外的空间作为临时存储，而不需要考虑清理使用的临时空间的操作。

Answer 1

正如其他人所指出的，您可以使用 O(n) counting sort .但是，您还需要考虑一些其他问题。我们假设您要存储 32 位整数，即 100GB ~ 27e9 整数。

如果所有整数都相同，那么它将出现 ~27e9 次，这比 32 位 int 大。因此，您的计数器必须是 64 位整数。

使用 2GB RAM，您一次只能在 RAM 中存储 ~125e6 个计数器。如果我们不能对整数的分布做出任何假设，我们要么必须:

• 单独增加 HD 上的计数器，或者
• 忽略我们遇到的所有不在我们当前存储在 RAM 中的计数器数组中的整数。

我认为后一种选择更好。由于我们需要 ~4e9 个 64 位计数器并且只能存储 2GB，因此我们需要遍历整个数组 ~16 次。如果我们考虑遇到诸如 0,1<<31,0 的整数序列，第一个选项显然不好。这些计数器不会同时存储在 RAM 中，因此至少需要 2 次 HD 写入。

因此，我认为对于您问题的具体大小 (100GB)，N-way merge sort 会更好，因为这只需要读取整个数组 log_2(100) ~ 8 次。

但是，如果面试官马上把问题改成“10TB数组，还是2GB内存”，那么计数排序就很容易胜出。