especie de "programación Scala" causa desbordamiento de pila

Question

Un corte directo y pegar el siguiente algoritmo:

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

provoca una StackOverflowError en 5000 listas largas.

¿Hay alguna manera de optimizar esto para que esto no ocurra?

Answer 1

Lo hace porque no es recursivo en la cola. Puede solucionar esto ya sea utilizando una colección no estricta o haciendo que sea recursiva.

La última solución es la siguiente:

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

Uso no rigor implica ya sea pasar parámetros por nombre, o el uso de colecciones no estrictas como Stream. El siguiente código utiliza Stream sólo para evitar desbordamiento de pila, y List en otra parte:

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

Sólo en caso de soluciones de Daniel no lo hacen lo suficientemente claro, el problema es la repetición de esa combinación es tan profunda como la longitud de la lista , y no es recursividad de cola por lo que no se puede convertir en iteración.

Scala puede convertir solución de combinación recursiva de cola de Daniel en algo aproximadamente equivalente a esto:

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 
} 

pero mantiene un registro de todas las variables para usted.

(Un método recursiva de cola es uno donde el método sólo hace llamar para obtener una respuesta completa a pasar hacia atrás;. Nunca se llama a sí mismo y luego hace algo con el resultado antes de pasar de nuevo también, cola-recursividad no se puede utilizar si el método puede ser polimórfico, por lo que generalmente solo funciona en objetos o con clases marcadas como finales.)

Answer 3

Solo jugando con scala's TailCalls (soporte trampolín), que sospecho que no existía cuando esto la pregunta fue planteada originalmente. Aquí hay una versión recursiva e inmutable de la combinación en 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 
} 

Corre tan rápido como la versión mutable en grandes List[Long] s sobre el Scala 2.9.1 en OpenJDK 64 bits (amd64 Debian/Squeeze en una i7).