Rendimiento de recursión en la lista de escalas

Question

Esta pregunta trata sobre la forma en que Scala realiza la coincidencia de patrones y la recursión con listas y el rendimiento de las mismas.

Si tengo una función que recursivamente a través de una lista y lo hago con juego en una contra, por ejemplo, algo como:

def myFunction(xs) = xs match { 
    case Nil => Nil 
    case x :: xs => «something» myFunction(xs) 
} 

En Haskell:

myFunction [] = [] 
myFunction (x:xs) = «something» : myFunction xs 

estoy usando la misma semántica que haría con, por ejemplo, Haskell. No creo que haya ninguna pregunta sobre la implementación de Haskell ya que es simplemente la forma en que manejas las listas. Para una larga lista (estaría operando en una lista con algunos miles de nodos), Haskell no parpadearía (me imagino, sin embargo, nunca lo intenté).

Pero por lo que sé con Scala, la declaración partido llamaría el método de extracción cancelar la aplicación de dividir la lista en torno a los contras y, para extender el ejemplo de una función que no hace nada a la lista:

def myFunction(xs) = xs match { 
    case Nil => Nil 
    case x :: xs => x :: myFunction(xs) 
} 

En Haskell:

myFunction [] = [] 
myFunction (x:xs) = x : myFunction xs 

sería llamar a aplicar el método de extracción de los contras de nuevo juntos. Para una larga lista, me imagino que esto sería muy caro.

Para ilustrar, en mi caso específico, quiero recurrir sobre una lista de caracteres y acumular varias cosas, donde la cadena de entrada es algo hasta algunas decenas de kilobytes.

¿Debo llamar realmente a los constructores y extractores para cada paso de la recursión si quiero recurse en una larga lista? ¿O hay optimizaciones? O mejores formas de hacerlo? En este caso necesitaría varias variables del acumulador y, obviamente, no sería sólo de manera recursiva a través de una lista de no hacer nada ...

(Por favor, disculpe mi Haskell, yo no he escrito una línea de dos años.)

(Y sí, voy por la recursión de cola.)

Answer 1

en primer lugar, Haskell no es estricta, por lo que estas llamadas de función en la cola no puede ser evaluado en absoluto. Scala, por otro lado, calculará toda la lista antes de regresar. Una implementación más cerca de lo que ocurre en Haskell sería la siguiente:

def myFunction[T](l: List[T]): Stream[T] = l match { 
    case Nil => Stream.empty 
    case x :: xs => x #:: myFunction(xs) 
} 

que recibe un List, que es estricta, y devuelve un Stream que no es estricta.

Ahora bien, si se quiere evitar a juego y extractores de patrones (aunque ninguno se llama en este caso particular - véase más adelante), que sólo podría hacer esto:

def myFunction[T](xs: List[T]): Stream[T] = 
    if (xs.isEmpty) Stream.empty else xs.head #:: myFunction(xs.tail) 

me he dado cuenta de que la intención de ir para la recursividad de la cola. Lo que escribió no es recursivo de cola, porque antepone x al resultado de la recursión.Al manejar listas, obtendrá la recursión de cola Si calcula los resultados hacia atrás y luego invertido:

def myFunction[T](xs: List[T]): List[T] = { 
    def recursion(input: List[T], output: List[T]): List[T] = input match { 
    case x :: xs => recursion(xs, x :: output) 
    case Nil => output 
    } 
    recursion(xs, Nil).reverse 
} 

pasado, vamos a descompilar un ejemplo para ver cómo funciona:

class ListExample { 
    def test(o: Any): Any = o match { 
    case Nil => Nil 
    case x :: xs => xs 
    case _ => null 
    } 
} 

Genera:

public class ListExample extends java.lang.Object implements scala.ScalaObject{ 
public ListExample(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."<init>":()V 
    4: return 

public java.lang.Object test(java.lang.Object); 
    Code: 
    0: aload_1 
    1: astore_2 
    2: getstatic  #18; //Field scala/Nil$.MODULE$:Lscala/Nil$; 
    5: aload_2 
    6: invokestatic #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z 
    9: ifeq 18 
    12: getstatic  #18; //Field scala/Nil$.MODULE$:Lscala/Nil$; 
    15: goto 38 
    18: aload_2 
    19: instanceof  #26; //class scala/$colon$colon 
    22: ifeq 35 
    25: aload_2 
    26: checkcast  #26; //class scala/$colon$colon 
    29: invokevirtual #30; //Method scala/$colon$colon.tl$1:()Lscala/List; 
    32: goto 38 
    35: aconst_null 
    36: pop 
    37: aconst_null 
    38: areturn 

public int $tag() throws java.rmi.RemoteException; 
    Code: 
    0: aload_0 
    1: invokestatic #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I 
    4: ireturn 

} 

Decoding, llama primero el método equals en el parámetro pasado y el objeto Nil. Devuelve el último si es verdadero. De lo contrario, llama al instanceOf[::] en el objeto. Si es verdadero, arroja el objeto a eso e invoca el método tl en él. Al fallar todo eso, carga el cosntant null y lo devuelve.

Así que, ves, x :: xs no está llamando a ningún extractor.

En cuanto a la acumulación, hay otro modelo es posible que desee considerar:

val list = List.fill(100)(scala.util.Random.nextInt) 
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0) 
val accumulator = list.foldLeft(Accumulator())((acc, n) => 
    n match { 
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1) 
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1) 
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1) 
    }) 

Los parámetros por defecto y copiar los métodos son una característica Scala 2.8 He utilizado sólo para hacer el ejemplo más simple, pero el punto es el uso de la foldLeft método cuando desea acumular cosas en una lista.