algorithm - 查找一个非常大的文件的 k-最大元素(当 k 非常大时)

Question

假设我们有一个非常大的文件，其中包含数十亿个整数，我们想要找到这些值的 k 个最大元素，

棘手的部分是 k 本身也非常大，这意味着我们不能在内存中保留 k 元素(例如我们有一个包含 100 亿个元素的文件我们想找到 100 亿个最大的元素)

我们如何在 O(n) 中做到这一点？

我的想法:

我们开始读取文件，并用另一个保持 k 最大元素(按递增顺序排列)的文件检查它，如果读取的元素大于第二个文件的第一行，我们删除第一行并将其插入到第二个文件中，时间复杂度为O(NlogK)(如果我们可以随机访问该文件，否则为'O(Nk)'

在 O(n) 中执行此操作的任何想法，我想如果我们有 Selection algorithm(快速排序中的分区算法)的外部版本，我们将能够在 O(n) 中执行此操作，但我无法在任何地方找到它

Answer 1

您可以使用标准合并类型算法轻松完成此操作。

假设您有 1000 亿个数字，您想要前 100 亿个。我们假设您随时可以在内存中保存 10 亿个数字。

所以你通过了:

while not end of input
    read 1 billion numbers
    sort them in descending order
    save position of output file
    write sorted numbers to output file

然后您有一个文件，其中包含 100 个 block ，每个 block 包含 10 亿个数字。每个 block 按降序排序。

现在创建一个最大堆。将每个 block 的第一个数字添加到堆中。您还必须添加 block 编号或编号在文件中的位置，以便您可以读取下一个编号。

然后:

while num_selected < 10 billion
    selected = heap.remove()
    ++num_selected
    write selected to output
    read next number from the selected block and place on heap

这涉及到一点点复杂性，跟踪数字来自哪个区 block ，但还算不错。

最大堆永远不会包含超过 100 个项目(基本上，每个 block 一个项目)，因此内存在第二遍中不是问题。通过一些工作，您可以通过为每个 block 创建一个较小的缓冲区来避免大量读取，这样您就不会为每个选定的数字产生磁盘读取成本。

它基本上只是一种磁盘合并排序，但有一个早期输出。

第一遍的复杂度为 b * (m log m)，其中 b 是 block 数，m 是 block 中的项目数。 N，文件中的项目总数，等于 b * m。第二遍的复杂度为 k log b，其中 k 是要选择的项目数，b 是 block 数。