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

找到第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的每个“迭代”(在此上下文中这是正确的术语？)之后，我增加了要调用的函数堆栈，以使下一个元素加一吗？

我在网上找到的一种不求助于迭代解决方案(我希望避免进入功能编程/惯用标量法)的解决方案是this(问题7):

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

从我所看到的，这不会导致这种类似递归的方式。这是一个好方法吗，还是您知道更好的方法呢？

最佳答案

速度缓慢的原因之一是并不是eratosthenes筛子的。阅读http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf以获得详细说明(示例在Haskell中，但可以直接翻译成Scala)。

我对Euler问题＃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可以收集结果，并且可以由生成函数进行查询，因此您总是从头开始进行重新计算。