algorithm - 快速函数归并排序

Question

这是我在 Scala 中实现的合并排序:

object FuncSort {
  def merge(l: Stream[Int], r: Stream[Int]) : Stream[Int] = {
    (l, r) match {
      case (h #:: t, Empty) => l
      case (Empty, h #:: t) => r
      case (x #:: xs, y #:: ys) => if(x < y ) x #:: merge(xs, r) else y #:: merge(l, ys)
    }
  }

  def sort(xs: Stream[Int]) : Stream[Int] = {
    if(xs.length == 1) xs
    else {
      val m = xs.length / 2
      val (l, r) = xs.splitAt(m)
      merge(sort(l), sort(r))
    }
  }
}

它工作正常，似乎渐近地它也很好，但它比这里的 Java 实现慢得多(大约 10 倍)http://algs4.cs.princeton.edu/22mergesort/Merge.java.html并使用大量内存。是否有更快的功能性合并排序实现？显然，可以逐行移植 Java 版本，但这不是我想要的。

UPD:我已将 Stream 更改为 List 并将 #:: 更改为 :: 和排序例程变得更快，只比 Java 版本慢三到四倍。但是我不明白为什么它不会因堆栈溢出而崩溃？ merge 不是尾递归的，所有参数都经过严格评估...这怎么可能？

Answer 1

您提出了多个问题。我尽量按逻辑顺序回答:

Stream 版本没有堆栈溢出

你并没有真正问这个问题，但它导致了一些有趣的观察。

在 Stream 版本中，您在 merge 函数内使用 #::merge(...)。通常这是一个递归调用，可能会导致足够大的输入数据堆栈溢出。但在这种情况下不是。运算符 #::(a,b) 在 class ConsWrapper[A] 中实现(存在隐式转换)并且是 cons.apply 的同义词[A](hd: A, tl: ⇒ Stream[A]): Cons[A]。如您所见，第二个参数是按名称调用的，这意味着它是延迟计算的。

这意味着 merge 返回一个新创建的类型为 cons 的对象，它最终会再次调用 merge。换句话说:递归不是发生在栈上，而是发生在堆上。通常你有足够的堆。

使用堆进行递归是处理非常深的递归的好方法。但它比使用堆栈要慢得多。所以你用速度换取了递归深度。这就是使用 Stream 如此缓慢的主要原因。

第二个原因是，为了获得Stream的长度，Scala必须具体化整个Stream。但是在对 Stream 进行排序期间，它无论如何都必须具体化每个元素，所以这不会造成太大伤害。

List版本没有堆栈溢出

当你把 Stream 换成 List 的时候，你确实是在用栈来递归。现在可能会发生堆栈溢出。但是对于排序，您通常具有 log(size) 的递归深度，通常是以 2 为底的对数。因此，要对 40 亿个输入项目进行排序，您需要大约 32 个堆栈框架。默认堆栈大小至少为 320k(在 Windows 上，其他系统具有更大的默认值)，这为大量递归留出了空间，因此为大量输入数据进行了排序。

更快的功能实现

这取决于:-)

你应该使用栈，而不是堆来进行递归。你应该根据输入数据决定你的策略:

1. 对于小数据 block ，使用一些直接的算法对它们进行排序。算法的复杂性不会影响您，而且您可以通过将所有数据都放入缓存中来获得大量性能。当然你也可以手写sorting networks对于给定的尺寸。
2. 如果你有数字输入数据，你可以使用radix sort并处理处理器或 GPU 上的向量单元的工作(更复杂的算法可以在 GPU Gems 中找到)。
3. 对于中等大小的数据 block ，您可以使用分而治之的策略将数据拆分到多个线程(前提是您有多个内核!)
4. 对于巨大的数据 block ，使用合并排序并将其拆分为适合内存的 block 。如果需要，您可以将这些 block 分布在网络上并在内存中排序。

不要使用交换并使用你的缓存。如果可以，请使用可变数据结构并就地排序。我认为功能排序和快速排序不能很好地协同工作。要真正快速地进行排序，您将必须使用有状态操作(例如，可变数组上的就地合并排序)。

我通常在我的所有程序中尝试这样做:尽可能使用纯函数式风格，但在可行的情况下对小部分使用有状态操作(例如，因为它具有更好的性能，或者代码只需要处理很多状态并且变得很多当我使用 var 而不是 val 时，可读性更好。