Merge Art, die aus „Programming Scala“ Stapelüberlauf verursacht

Question

Eine direkte Ausschneiden und Einfügen des folgenden Algorithmus:

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

verursacht eine Stackoverflow auf 5000 langen Listen.

Gibt es eine Möglichkeit, dies zu optimieren, so dass dies nicht auftritt?

Answer 1

Es tut dies, weil es nicht tail-rekursiv ist. Sie können dies beheben, indem Sie entweder eine nicht-strikte Sammlung verwenden oder sie tailrekursiv machen.

Letztere Lösung geht so:

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

Die Verwendung von nicht-Strikt beinhaltet entweder Gabe von Parametern nach Name oder die Verwendung nicht-strengen Sammlungen wie Stream. Der folgende Code verwendet Stream nur Stack-Überlauf zu verhindern, und List an anderer Stelle:

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

Answer 2

Nur für den Fall Daniels Lösungen nicht klar genug machen, ist das Problem, dass merge Rekursion so tief wie die Länge der Liste ist und es handelt sich nicht um eine Tail-Rekursion, so dass es nicht in Iteration konvertiert werden kann.

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 
} 

aber es hält den Überblick über alle Variablen für Sie:

Scala kann etwas Daniels Schwanz-rekursive merge Lösung in etwa entspricht dies umzusetzen.

(A tail-rekursive Methode ist eine, wo das Verfahren nur nennt sich eine vollständige Antwort, um wieder zu passieren;. Sie nie selbst nennt und dann etwas tut, mit dem Ergebnis, bevor es wieder vorbei Auch Schwanz-Rekursion kann nicht verwendet werden, wenn die Methode möglicherweise polymorph ist, so dass sie im Allgemeinen nur in Objekten oder mit als final markierten Klassen funktioniert.)

Answer 3

Ich spiele gerade mit scalas TailCalls (Trampolin-Unterstützung) herum, von dem ich vermutete, dass es nicht dabei war Frage wurde ursprünglich gestellt. Hier ist eine rekursive unveränderliche Version der Zusammenführung in 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 
} 

Läuft genauso schnell wie die veränderbare Version auf großen List[Long] s auf Scala 2.9.1 auf 64-Bit-OpenJDK (Debian/Squeeze amd64 auf einem i7).