performance - Why is filter in front of foldLeft slow in Scala? -

i wrote answer first project euler question:

add natural numbers below 1 thousand multiples of 3 or 5.

the first thing came me was:

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

but it's slow (it takes 125 ms), rewrote it, thinking of 'another way' versus 'the faster way'

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

this faster (only 2 ms). why? i'm guess second version uses range generator , doesn't manifest realized collection in way, doing in 1 pass, both faster , less memory. right?

here code on ideone: http://ideone.com/gbklp

the problem, others have said, filter creates new collection. alternative withfilter doesn't, doesn't have foldleft. also, using .view, .iterator or .tostream avoid creating new collection in various ways, slower here first method used, thought strange @ first.

but, then... see, 1 until 1000 range, size small, because doesn't store each element. also, range's foreach extremely optimized, , specialized, not case of of other collections. since foldleft implemented foreach, long stay range enjoy optimized methods.

(_: range).foreach:

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

(_: range).view.foreach

def foreach[u](f: => 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] serializable {   private var = start    def hasnext: boolean = < end    def next: =      if (i < end) {       val x = self(i)       += 1       x     } else iterator.empty.next    def head =      if (i < end) self(i) else iterator.empty.next    /** $super    *  '''note:''' `drop` overridden enable fast searching in middle of indexed sequences.    */   override def drop(n: int): iterator[a] =     if (n > 0) new elements(i + n, end) else    /** $super    *  '''note:''' `take` overridden symmetric `drop`.    */   override def take(n: int): iterator[a] =     if (n <= 0) iterator.empty.buffered     else if (i + n < end) new elements(i, + n)      else } 

(_: range).view.iterator.foreach

def foreach[u](f: =>  u) { while (hasnext) f(next()) } 

and that, of course, doesn't count filter between view , foldleft:

override def filter(p: => boolean): = newfiltered(p).asinstanceof[this]  protected def newfiltered(p: => boolean): transformed[a] = new filtered { val pred = p }  trait filtered extends transformed[a] {   protected[this] val pred: => boolean    override def foreach[u](f: => u) {     (x <- self)       if (pred(x)) f(x)   }   override def stringprefix = self.stringprefix+"f" }