对1万亿整数进行排序

Question

给定硬盘上的1万亿个整数，找出其中最小的100万个。一次最多可以在内存中容纳100万个整数。

一种方法是，从1万亿中取出第一个100万，对100万个整数进行排序，并将其存储在硬盘中。这样，对每组100万个整数进行排序，并将其存储在硬盘中。现在，由100万个整数组成的组被排序了多达1万亿个。现在比较所有排序组的第一个元素，它们的最小值是1万亿的最小值。将其存储为内存中的第一个元素。接下来，从最小元素的组中获取第二个元素，然后与所有其他groups元素一起检查它。这样，重复这个过程，直到第一个100万被排序并存储在内存中为止。

有没有更好的方法，我错过了？

Answer 1

通过使用堆，可以在O(n日志m)中有效地完成这一任务。(n=所有数字，m=您想要找到的一组数字的大小)。

一次只看一万亿个数字。对于每个新数字，请执行以下操作之一。

1. 如果堆有<100万个节点，则将新编号插入堆中。
2. 如果堆正好有100万个节点，且顶部节点大于新编号，则从堆中弹出顶节点，并插入一个具有新编号的节点。
3. 如果没有1或2是真的，那么抛出这个数字。

在遍历完所有的万亿个条目之后，生成的堆将拥有最小的100万个数字。

从堆中插入和删除的是O(log )。单次通过堆的次数是n，所以算法是n*log (m)。

Answer 2

整数有多大？如果它们只是32位值，我只需在磁盘上创建一个由40亿个64位计数器组成的数组，当在输入中遇到x时，在x位置增加计数器。一般来说，这种方法在空间上是非常昂贵的，但是当可能的元素值的范围远远小于要排序的项目数时，成本就会相当低，而且最好的是它是及时的O(n)。

Answer 3

一个scala的解决方案，但不是针对1万亿元素的解决方案。当指针指向文件而不是列表或多个小列表时，可以这样做：

def top (n: Int, li: List [Int]) : List[Int] = {

  def updateSofar (sofar: List [Int], el: Int) : List [Int] = {
    // println (el + " - " + sofar)
    if (el < sofar.head) 
      (el :: sofar.tail).sortWith (_ > _) 
    else sofar
  }

  /* better readable:
    val sofar = li.take (n).sortWith (_ > _)
    val rest = li.drop (n)
    (sofar /: rest) (updateSofar (_, _)) */    
  (li.take (n). sortWith (_ > _) /: li.drop (n)) (updateSofar (_, _)) 
}

以前百万元素为例。把它们分类。现在，对于每一个跟随的元素，将其与百万中最大的元素进行比较。如果它较小，将其排序到列表中，并删除旧的最大值。