这是我在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
为toList
和#::
to ::
,并且排序例程变得更快,仅比Java版本慢三到四倍。但是我不明白为什么它不会因堆栈溢出而崩溃?merge
不是尾递归,所有参数都经过严格评估...这怎么可能?
您提出了多个问题。我尝试按照逻辑顺序回答它们:
您并没有真正问过这个问题,但是它带来了一些有趣的发现。
在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
,无论如何都必须实现每个元素,因此这不会造成很大的伤害。
当您更改Stream for List时,实际上是在使用堆栈进行递归。现在可能会发生堆栈溢出。但是通过排序,您的递归深度log(size)
通常为,通常为base的对数2
。因此,要对40亿个输入项进行分类,您将需要大约32个堆栈帧。默认堆栈大小至少为320k(在Windows上,其他系统具有更大的默认值),因此有很多递归空间,因此可以对许多输入数据进行排序。
这取决于 :-)
您应该使用堆栈,而不要使用堆进行递归。您应该根据输入数据决定策略:
不要使用swap并使用缓存。如果可以并使用适当的位置,请使用可变数据结构。我认为功能性排序和快速排序不能很好地协同工作。为了使排序真正快速,您将必须使用有状态操作(例如,可变数组上的就地归并排序)。
我通常在我的所有程序上都尝试这样做:尽可能使用纯函数样式,但在可行的情况下对小部分使用有状态的操作(例如,因为它具有更好的性能,或者代码只需要处理很多状态,并且在处理时会变得更好可读)我用var
s代替val
s)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句