为什么这个scala prime代这么慢/内存密集？

发布时间：2020-12-16 09:26:13 所属栏目：安全来源：网络整理

导读：我在找到第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[

我在找到第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))
  }
}

这是因为在每次“迭代”(这是这个上下文中的正确术语吗？)之后,我增加要调用的函数堆栈以使下一个元素一个一个？

我在网上发现的一个解决方案是不使用迭代解决方案(我想避免进入函数式编程/惯用scala)是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).

我对欧拉问题#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
    }
}

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!