首页 文章

排序1万亿整数

提问于
浏览 次
10

鉴于硬盘上有一组1万亿个整数，找到最小的100万个整数 . 一次最多可以在内存中容纳100万个整数 .

一种方法是，从1万亿中取出前100万个并对100万个整数进行排序并将其存储回硬盘中 . 通过这种方式对每组100万个整数进行排序并将其存储在硬盘中 . 现在，100万个整数的组合分类达1万亿 . 现在比较所有排序组的第一个元素，它们的最小值是1万亿的最小值 . 将其存储为内存中的第一个元素 . 接下来，从最小元素所在的组中取出第二个元素，然后使用所有其他组的第一个元素进行检查 . 以这种方式重复该过程，直到第一个100万被分类并存储在存储器中 .

我缺少一种更优化的方法吗？

algorithm sorting

4 回答

  • -1

    您可以使用heap在O（n log m）中有效地执行此操作 . （n =所有数字，m =您要查找的数字集的大小） .

    一次通过一万亿个数字 . 对于每个新号码，请执行以下操作之一 .

    • 如果堆有<1百万个节点，则将新数字插入堆中 .

    • 如果堆只有100万个节点且顶部节点大于新数，则从堆中弹出顶部节点，然后插入带有新编号的节点 .

    • 如果1或2都不为真，则抛出数字 .

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

    从堆中插入和删除是O（log m） . 通过堆的单次传递是n . 所以，算法是n * log（m）

    回复于
  • 1

    整数有多大？如果它们只是32位值，我只需在磁盘上创建一个包含40亿个64位计数器的数组，并在输入中遇到 x 时，将计数器递增到 x 位置 . 一般来说，这种方法在空间上的成本非常高，但只要可能的元素值的范围远小于要排序的项目的数量，成本就会很低，最重要的是它的时间是 O(n) .

    回复于
  • 29

    scala中的解决方案，但不适用于1万亿个元素 . 使用指向文件而不是List或多个小列表的指针，可以通过以下方式完成：

    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 (_, _)) 
}

    拿出第一百万个元素 . 排序他们 . 现在，对于每个后续元素，将其与百万中的最大元素进行比较 . 如果它更小，则将其排序到列表中并删除旧的最大值 .

    回复于
  • -2

    您可以在O（n）时间内使用QuickSort的变体更有效地执行此操作，其中'n'是磁盘上列表的大小 . （在这种情况下是万亿）

    你所要做的就是：

    • 通过在越来越小的部分中多次分区磁盘驱动器，找到百万分之一的最小数字 . 这需要O（n）时间 .

    • 把它和分区已经整理好的其他999,999个整数放在RAM中 . 你完成了 .

    最小的百万整数将不会被排序，但它们将是最小的百万 .

    如果你想要排序最小的百万，那么它需要O（m log m）时间，在这种情况下'm'是一百万 .

    没有空间成本，O（n）时间，使用非整数值 . 请享用 . :)

    回复于

相关问题