Alex Rivera | Logout

Why is filter in front of foldLeft slow in Scala?

Asked 2011-01-25T16:00:05.053
20

I wrote an answer to the first Project Euler question:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

The first thing that came to me was:

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

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

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

This is much faster (only 2 ms). Why? I'm guess the second version uses only the Range generator and doesn't manifest a fully realized collection in any way, doing it all in one pass, both faster and with less memory. Am I right?

Here the code on IdeOne: http://ideone.com/GbKlP

performance scala scala-collections
Edit
Report

1 Answer

3

Looking through the code, it looks like filter does build a new Seq on which the foldLeft is called. The second skips that bit. It's not so much the memory, although that can't but help, but that the filtered collection is never built at all. All that work is never done.

Range uses TranversableLike.filter, which looks like this: 

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

I think it's the += on line 4 that's the difference. Filtering in foldLeft eliminates it.

answered 2011-01-25T16:13:41.380

Your Answer