Why Stream/lazy val implementation using is faster than ListBuffer one
- by anrizal
I coded the following implementation of lazy sieve algorithms using Stream and lazy val below :
def primes(): Stream[Int] = {
lazy val ps = 2 #:: sieve(3)
def sieve(p: Int): Stream[Int] = {
p #:: sieve(
Stream.from(p + 2, 2).
find(i=> ps.takeWhile(j => j * j <= i).
forall(i % _ > 0)).get)
}
ps
}
and the following implementation using (mutable) ListBuffer:
import scala.collection.mutable.ListBuffer
def primes(): Stream[Int] = {
def sieve(p: Int, ps: ListBuffer[Int]): Stream[Int] = {
p #:: { val nextprime =
Stream.from(p + 2, 2).
find(i=> ps.takeWhile(j => j * j <= i).
forall(i % _ > 0)).get
sieve(nextprime, ps += nextprime)
}
}
sieve(3, ListBuffer(3))}
When I did primes().takeWhile(_ < 1000000).size , the first implementation is 3 times faster than the second one.
What's the explanation for this ?
I edited the second version: it should have been sieve(3, ListBuffer(3)) instead of sieve(3, ListBuffer()) .
