为什么这个scala素数生成如此缓慢/密集的内存? [英] Why is this scala prime generation so slow/memory intensive?

问题描述

我发现第10,001个素数时内存不足.

I run out of memory while finding the 10,001th prime number.

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的迭代"(在此上下文中这是正确的术语?)之后，我都会增加要调用的函数堆栈，以使下一个元素加一吗?

Is this because after each "iteration" (is this the correct term in this context?) of primes, I increase the stack of functions to be called to get the next element by one?

我在网络上找到的一种解决方案是

One solution that I've found on the web which doesn't resort to an iterative solution (which I'd like to avoid to get into functional programming/idiomatic scala) is this (Problem 7):

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

据我所见，这不会导致这种类似于递归的方式.是这样做的好方法，还是您知道更好的方法?

From what I can see, this does not lead to this recursion-like way. Is this a good way to do it, or do you know of a better way?

推荐答案

之所以如此缓慢，一个原因是它不是筛网的筛子.阅读 http://www.cs.hmc.edu/~oneill/论文/Sieve-JFP.pdf 获取详细说明(示例在Haskell中，但可以直接翻译成Scala).

One reason why this is slow is that it isn't the sieve of Eratosthenes. Read http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf for a detailled explanation (the examples are in Haskell, but can be translated directly into Scala).

我对Euler问题#7的旧解决方法也不是真正的"筛子，但是对于少量数字来说，它似乎已经足够好了:

My old solution for Euler problem #7 wasn't the "true" sieve either, but it seems to work good enough for little numbers:

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 s而没有val可以收集结果，并且可以由生成函数查询，因此您总是从头开始重新计算.

I think the problem with your first version is that you have only defs and no val which collects the results and can be consulted by the generating function, so you always recalculate from scratch.

这篇关于为什么这个scala素数生成如此缓慢/密集的内存?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！