为什么使用流/懒阀实现的速度比ListBuffer更快

Question

我使用流和懒阀以下编码以下懒筛算法的实现：

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（）。时（_ <1000000）。大小时，第一个实现比第二个实现快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.

Answer 2

不是真正回答这个问题，但是由于我花了一些时间基准了各种组合...

如果您使用的话，您可以获得更好的性能 Iterator, ArrayBuffer 并避免 takeWhile 在内部循环中，以最大程度地减少内存分配。

def primes2(): Stream[Int] = {
  def sieve(p: Int, ps: ArrayBuffer[Int]): Stream[Int] = {
    def hasNoDivisor(prime_? :Int, j: Int = 0): Boolean = {
      val n = ps(j)
      if (n*n > prime_?) true
      else if (prime_? % n == 0) false else hasNoDivisor(prime_?, j+1)
    }
    p #:: { 
      val nextprime = Iterator.from(ps.last + 2, 2).find(hasNoDivisor(_)).get
      sieve(nextprime, ps += nextprime)
    }
  }     
  sieve(3, ArrayBuffer(3))
}

这是一个版本 Iterator 代替 Stream, ，它更快，您可以随时使用 primes3().toStream 如果需要，要获取流。

def primes3() = List(2,3).iterator ++ new Iterator[Int] {
  val ps = ArrayBuffer[Int](3)
  def hasNoDivisor(prime_? :Int, j: Int = 0): Boolean = {
    val n = ps(j)
    if (n*n > prime_?) true
    else if (prime_? % n == 0) false else hasNoDivisor(prime_?, j+1)
  }
  def hasNext = true
  def next() = {
    val nextprime = Iterator.from(ps.last + 2, 2).find(hasNoDivisor(_)).get
    ps += nextprime
    nextprime
  }
}

结果：

primes : warming...
primes : running...
primes : elapsed: 3.711
res39: Int = 283145
primes2: warming...
primes2: running...
primes2: elapsed: 1.039
res40: Int = 283145
primes3: warming...
primes3: running...
primes3: elapsed: 0.530
res41: Int = 283146

我也尝试更换 from, find 和 hasNoDivisor 有几个 while 循环，这速度更快，但较不容易理解。