scala - 为什么这个 scala 素数生成如此慢/内存密集？

Question

在查找第 10,001 个质数时，我的内存不足。

object Euler0007 {
  def from(n: Int): Stream[Int] = n #:: from(n + 1)
  def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
  def primes = sieve(from(2))
  def main(args: Array[String]): Unit = {
    println(primes(10001))
  }
}

这是因为在primes的每次“迭代”(在这种情况下这是正确的术语吗？)之后，我将要调用的函数堆栈增加一以获取下一个元素？

我在网上找到的一个不诉诸迭代解决方案的解决方案(我想避免进入函数式编程/惯用的 scala)是 this (问题7):

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

据我所知，这不会导致这种类似递归的方式。这是一个好方法吗？或者您知道更好的方法吗？

Answer 1

速度缓慢的一个原因是它不是埃拉托色尼筛法。阅读 http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf详细解释(示例是 Haskell 语言，但可以直接翻译成 Scala)。

我对欧拉问题 #7 的旧解决方案也不是“真正的”筛子，但它似乎对于小数字来说已经足够好了:

object Sieve {

    val primes = 2 #:: sieve(3)

    def sieve(n: Int) : Stream[Int] =
          if (primes.takeWhile(p => p*p <= n).exists(n % _ == 0)) sieve(n + 2)
          else n #:: sieve(n + 2)

    def main(args: Array[String]) {
      println(primes(10000)) //note that indexes are zero-based
    }
}

我认为你的第一个版本的问题是你只有 def 而没有 val 来收集结果并可以由生成函数查阅，所以你总是从头开始重新计算。