归并排序导致堆栈溢出

问题描述：

def msort[T](less: (T, T) => Boolean) 
      (xs: List[T]): List[T] = { 
    def merge(xs: List[T], ys: List[T]): List[T] = 
    (xs, ys) match { 
     case (Nil, _) => ys 
     case (_, Nil) => xs 
     case (x :: xs1, y :: ys1) => 
     if (less(x, y)) x :: merge(xs1, ys) 
     else y :: merge(xs, ys1) 
    } 
    val n = xs.length/2 
    if (n == 0) xs 
    else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs)) 
    } 
}

导致的*Error 5000成上一长串。

有没有什么办法来优化这个，这样不会发生？

答

这样做是因为它不是尾递归。您可以通过使用非严格的集合或通过尾递归来解决此问题。

将后者溶液是这样的：

def msort[T](less: (T, T) => Boolean) 
      (xs: List[T]): List[T] = { 
    def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] = 
    (xs, ys) match { 
     case (Nil, _) => ys.reverse ::: acc 
     case (_, Nil) => xs.reverse ::: acc 
     case (x :: xs1, y :: ys1) => 
     if (less(x, y)) merge(xs1, ys, x :: acc) 
     else merge(xs, ys1, y :: acc) 
    } 
    val n = xs.length/2 
    if (n == 0) xs 
    else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs), Nil).reverse 
    } 
}

使用非严格性涉及或者通过名称传递参数，或使用非严格的集合，如Stream。下面的代码使用Stream只是为了防止堆栈溢出，并List别处：

def msort[T](less: (T, T) => Boolean) 
      (xs: List[T]): List[T] = { 
    def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match { 
    case (x :: xs, y :: ys) if less(x, y) => Stream.cons(x, merge(xs, right)) 
    case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys)) 
    case _ => if (left.isEmpty) right.toStream else left.toStream 
    } 
    val n = xs.length/2 
    if (n == 0) xs 
    else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs)).toList 
    } 
}

我曾试图让它尾递归，然后看到了很多信息，声称JVM不适合，并且不总是优化尾递归。有什么指导方针可以成功吗？ – user44242 2010-02-04 20:00:23

JVM没有，所以Scala编译器会为你做。它只在一定的要求下做到：它必须是自递归的（即f调用g，g调用f将不起作用），当然它必须是_tail_递归（递归调用_must_总是最后一件事）代码路径），方法必须是“final”或“private”。在这个例子中，因为'merge'是在'msort'内部定义的，而不是在一个类或对象上定义的，它实际上是私有的。 – 2010-02-04 20:29:53

我认为这里值得一提的是，msort本身并不是尾递归，而是合并。对于只有编译器相信的人来说，将@tailrec添加到合并的定义中，您会注意到它已被接受为尾递归函数，就像Daniel概括的那样。 – 2011-01-29 19:40:54

答

万一丹尼尔的解决方案没能不够清晰，问题是，合并的递归是深如列表的长度，它不是尾递归，所以它不能转换为迭代。

斯卡拉可以丹尼尔的尾递归合并方案转换成东西约相当于此：

def merge(xs: List[T], ys: List[T]): List[T] = { 
    var acc:List[T] = Nil 
    var decx = xs 
    var decy = ys 
    while (!decx.isEmpty || !decy.isEmpty) { 
    (decx, decy) match { 
     case (Nil, _) => { acc = decy.reverse ::: acc ; decy = Nil } 
     case (_, Nil) => { acc = decx.reverse ::: acc ; decx = Nil } 
     case (x :: xs1, y :: ys1) => 
     if (less(x, y)) { acc = x :: acc ; decx = xs1 } 
     else { acc = y :: acc ; decy = ys1 } 
    } 
    } 
    acc.reverse 
}

，但它会跟踪你所有的变量。（尾递归方法是一种方法，其中方法只有调用它自己才能得到一个完整的回传;它从不会调用它自己，然后在返回结果之前对结果做一些处理，而且，尾递归如果方法可能是多态的，所以它通常只适用于对象或类标记为final。）

如果最后一个acc实际上是acc.reverse？如果你使用这个作为独立的合并函数应该有，但也许有关于msort的用法我没有得到。 – timday 2013-01-13 15:37:38

@timday - 对。固定。 – 2013-01-13 17:25:05

答

只是玩弄斯卡拉TailCalls（蹦床支持），我怀疑这是不是在这个时候问题最初提出。下面是Rex's answer中合并的递归不可变版本。

import scala.util.control.TailCalls._ 

def merge[T <% Ordered[T]](x:List[T],y:List[T]):List[T] = { 

    def build(s:List[T],a:List[T],b:List[T]):TailRec[List[T]] = { 
    if (a.isEmpty) { 
     done(b.reverse ::: s) 
    } else if (b.isEmpty) { 
     done(a.reverse ::: s) 
    } else if (a.head<b.head) { 
     tailcall(build(a.head::s,a.tail,b)) 
    } else { 
     tailcall(build(b.head::s,a,b.tail)) 
    } 
    } 

    build(List(),x,y).result.reverse 
}

运行得一样快，在大List[Long] S上的可变版本上的Scala 2.9.1上64位的OpenJDK（Debian的/挤压AMD64上I7）。

归并排序导致堆栈溢出

相关推荐