为什么Stream/lazy val实现使用比ListBuffer快

Question

我在下面使用Stream和lazy val编写了以下懒惰筛选算法的实现:

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
}

以及使用(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))}

当我做primes().takeWhile(_ <1000000).size时,第一个实现比第二个实现快3倍.对此有何解释？

我编辑了第二个版本:它应该是筛子(3,ListBuffer(3))而不是筛子(3,ListBuffer()).

Answer 1

好吧,我的猜测就是这一行:

find(i=> ps.takeWhile(j => j * j <= i).forall(i % _ > 0)).get

在ListBuffer,takeWhile创建一个临时集合(不断变得越来越大).同时,Stream由于其不严格,避免这样做.一旦forall失败,它就会停止计算takeWhile.