快速功能合并排序

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

您提出了多个问题。我尝试按逻辑顺序回答这些问题：

\n\n

Stream 版本中没有堆栈溢出

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

List版本没有堆栈溢出

\n\n

当您将 Stream 更改为 List 时，您实际上是在使用堆栈进行递归。现在可能会发生堆栈溢出。但对于排序，通常的递归深度log(size)通常是底数的对数2。因此，要对 40 亿个输入项进行排序，您将需要大约 32 个堆栈帧。默认堆栈大小至少为 320k（在 Windows 上，其他系统具有更大的默认值），这为大量递归留下了空间，从而为大量输入数据进行排序。

\n\n

更快的功能实现

\n\n

这取决于 ：-）

\n\n

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

\n\n

\n
1. 对于小数据块，使用一些直接的算法对它们进行排序。算法的复杂性不会影响您，并且您可以通过将所有数据放入缓存中来获得大量性能。当然，您仍然可以针对给定的大小手动进行代码排序网络。
\n
2. 如果您有数字输入数据，则可以使用基数排序并将工作处理到处理器或 GPU 上的向量单元（可以在GPU Gems中找到更复杂的算法）。
\n
3. 对于中等大小的数据块，您可以使用分而治之的策略将数据拆分到多个线程（前提是您有多个核心！）
\n
4. 对于巨大的数据块，使用合并排序并将其拆分为适合内存的块。如果需要，您可以将这些块分布在网络上并在内存中排序。
\n

\n\n

不要使用交换并使用缓存。如果可以的话，使用可变数据结构并就地排序。我认为函数式排序和快速排序不能很好地结合在一起。为了使排序真正快速，您必须使用有状态操作（例如可变数组上的就地合并排序）。

\n\n

我通常在我的所有程序上尝试这样做：尽可能使用纯函数式风格，但在可行的情况下对小部分使用有状态操作（例如，因为它具有更好的性能，或者代码只需要处理大量状态，并且在以下情况下变得更好可读）我用vars 而不是vals)。

\n