查找非常大的文件的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个块,每个块包含10亿个数字.每个块按降序排序.

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

然后:

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

涉及到一些复杂性,跟踪数字来自哪个块,但它并不是太糟糕.

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

它基本上只是一个磁盘合并排序,但提前了.

第一遍的复杂性是b * (m log m),其中b是块的数量,m是块中的项目数.N,文件中的项目总数等于b * m.第二遍的复杂性是k log b,k要选择的项目数在哪里,b是块的数量.

Answer 2

PS：我对K的定义不同。它是一个很小的数字，比如 2、100 或 1000。这里 m 对应于 OPS 对 k 的定义。为此事道歉。

取决于您可以对原始数据进行多少次读取以及您还有多少空间。这种方法假设您有相当于原始数据的额外空间。

第 1 步：在整个数据中选取 K 个随机数
第 2 步：对 K 个数字进行排序（假设索引从 1 到 K）
第 3 步：创建 K+1 个单独的文件并将它们命名为 0 到 K
第 4 步：对于数据，如果它在第 i 个和第 i+th 元素之间，则将其放入第 i 个文件中。
步骤5：根据每个文件的大小，选择第m个编号的文件。
步骤 6：使用新文件和新 m 重复所有操作（new_m = m - sum_of_size_of_all_lower_files）

关于最后一步，如果 K=2、m=1000 并且文件 0 的大小为 800、1 为 900、2 为 200，则 new_m = m-800 = 200 并迭代处理文件 1。