¿Por qué el filtro delante de foldLeft es lento en Scala?

Question

me escribió una respuesta a la primera pregunta Project Euler:

Añadir todos los números naturales por debajo de mil que son múltiplos de 3 o 5.

La primera cosa que me vino fue:

(1 until 1000).filter(i => (i % 3 == 0 || i % 5 == 0)).foldLeft(0)(_ + _) 

pero es lento (tarda 125   ms), por lo que volvió a escribir, simplemente pensando en 'otra manera' frente a 'la forma más rápida'

(1 until 1000).foldLeft(0){ 
    (total, x) => 
     x match { 
      case i if (i % 3 == 0 || i % 5 ==0) => i + total // Add 
      case _ => total //skip 
     } 
} 

Esto es mucho más rápido (solo 2   ms). ¿Por qué? Supongo que la segunda versión usa solo el generador de rango y no manifiesta una colección completamente realizada de ninguna manera, haciéndolo todo de una vez, más rápido y con menos memoria. ¿Estoy en lo cierto?

Aquí el código en Ideone: http://ideone.com/GbKlP

Answer 1

El problema, como han dicho otros, es que filter crea una nueva colección. La alternativa withFilter no, pero eso no tiene un foldLeft. Además, usar .view, .iterator o .toStream evitaría crear la nueva colección de varias maneras, pero aquí son más lentas que el primer método que usaste, lo cual me pareció algo extraño al principio.

Pero, entonces ...Ver, 1 until 1000 es un Range, cuyo tamaño es realmente muy pequeño, porque no almacena cada elemento. Además, Range 's foreach está extremadamente optimizado, e incluso es specialized, que no es el caso de ninguna de las otras colecciones. Dado que foldLeft se implementa como foreach, siempre que se quede con un Range podrá disfrutar de sus métodos optimizados.

(_: Range).foreach:

@inline final override def foreach[@specialized(Unit) U](f: Int => U) { 
    if (length > 0) { 
     val last = this.last 
     var i = start 
     while (i != last) { 
      f(i) 
      i += step 
     } 
     f(i) 
    } 
} 

(_: Range).view.foreach

def foreach[U](f: A => U): Unit = 
    iterator.foreach(f) 

(_: Range).view.iterator

override def iterator: Iterator[A] = new Elements(0, length) 

protected class Elements(start: Int, end: Int) extends BufferedIterator[A] with Serializable { 
    private var i = start 

    def hasNext: Boolean = i < end 

    def next: A = 
    if (i < end) { 
     val x = self(i) 
     i += 1 
     x 
    } else Iterator.empty.next 

    def head = 
    if (i < end) self(i) else Iterator.empty.next 

    /** $super 
    * '''Note:''' `drop` is overridden to enable fast searching in the middle of indexed sequences. 
    */ 
    override def drop(n: Int): Iterator[A] = 
    if (n > 0) new Elements(i + n, end) else this 

    /** $super 
    * '''Note:''' `take` is overridden to be symmetric to `drop`. 
    */ 
    override def take(n: Int): Iterator[A] = 
    if (n <= 0) Iterator.empty.buffered 
    else if (i + n < end) new Elements(i, i + n) 
    else this 
} 

(_: Range).view.iterator.foreach

def foreach[U](f: A => U) { while (hasNext) f(next()) } 

Y eso, por supuesto, ni siquiera las cuenten la filter entre view y foldLeft:

override def filter(p: A => Boolean): This = newFiltered(p).asInstanceOf[This] 

protected def newFiltered(p: A => Boolean): Transformed[A] = new Filtered { val pred = p } 

trait Filtered extends Transformed[A] { 
    protected[this] val pred: A => Boolean 
    override def foreach[U](f: A => U) { 
    for (x <- self) 
     if (pred(x)) f(x) 
    } 
    override def stringPrefix = self.stringPrefix+"F" 
} 

Answer 2

Mirando a través del código, parece que no filter construir una nueva Sec sobre la que se llama el foldLeft. El segundo se saltea ese bit. No es tanto la memoria, aunque eso no puede sino ayudar, pero que la colección filtrada nunca se construye en absoluto. Todo ese trabajo nunca termina.

Rango utiliza TranversableLike.filter, que se ve así:

def filter(p: A => Boolean): Repr = { 
    val b = newBuilder 
    for (x <- this) 
    if (p(x)) b += x 
    b.result 
} 

Creo que es la += en la línea 4 que es la diferencia. Filtrar en foldLeft lo elimina.

Answer 3

intentar hacer la colección perezosa en primer lugar, por lo

(1 until 1000).view.filter... 

en lugar de

(1 until 1000).filter... 

Eso debería evitar el costo de la construcción de una colección intermedia. También puede obtener un mejor rendimiento al usar sum en lugar de foldLeft(0)(_ + _), siempre es posible que algún tipo de recopilación tenga una forma más eficiente de sumar números. Si no, es aún más limpio y más declarativo ...

Answer 4

filter crea una secuencia completamente nueva en la que se llama entonces foldLeft. Proveedores:

(1 until 1000).view.filter(i => (i % 3 == 0 || i % 5 == 0)).reduceLeft(_+_)

Esto evitará que dicho efecto, simplemente envolviendo lo original. El intercambio de foldLeft con reduceLeft es solo cosmético (en este caso).

Answer 5

Ahora el reto es, se puede pensar en una forma aún más eficiente? No es que su solución sea demasiado lenta en este caso, pero ¿qué tan bien escala? ¿Qué pasa si en vez de 1000, fuera 1000000000? Hay una solución que podría calcular el último caso tan rápido como el primero.