歸併排序導致堆棧溢出

以下算法的直接剪切和粘貼：歸併排序導致堆棧溢出

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)) 
    } 
}

導致的StackOverflowError 5000成上一長串。

有沒有什麼辦法來優化這個，這樣不會發生？

來源

2010-02-04 user44242

這樣做是因爲它不是尾遞歸。您可以通過使用非嚴格的集合或通過尾遞歸來解決此問題。

將後者溶液是這樣的：

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 
    } 
}

來源

2010-02-04 18:43:51

我曾試圖讓它尾遞歸，然後看到了很多信息，聲稱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。）

來源

2010-02-04 20:11:10

如果最後一個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）。

來源

2013-01-13 15:28:13 timday

歸併排序導致堆棧溢出

回答

相關問題