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

Question

我使用下面的 Stream 和惰性 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
}

以及使用（可变）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 倍。对此有何解释？

我编辑了第二个版本：它应该是 sieve(3, ListBuffer(3)) 而不是 sieve(3, ListBuffer()) 。

Answer 1

好吧，我的猜测是这一行：

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

On ListBuffer，takeWhile创建一个临时集合（它越来越大）。同时，Stream由于其非严格性，避免这样做。一旦forall失败，它就会停止计算takeWhile.

Answer 2

没有真正回答这个问题，但因为我花了一些时间对各种组合进行基准测试......

如果在内部循环中使用并避免使用Iterator，您可以获得更好的性能，以最小化内存分配。ArrayBuffertakeWhile

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如果需要，您可以随时使用来获取 Stream。

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和，这样更快，但更难理解。hasNoDivisorwhile