Scala性能筛选
现在，我正在尝试学习Scala。我从小事做起，写了一些简单的算法。当我想通过查找所有低于某个阈值的素数来实现Sieve算法时，我遇到了一些问题。
我的实现是：
import scala.math
object Sieve {
// Returns all prime numbers until maxNum
def getPrimes(maxNum : Int) = {
def sieve(list: List[Int], stop : Int) : List[Int] = {
list match {
case Nil => Nil
case h :: list if h <= stop => h :: sieve(list.filterNot(_ % h == 0), stop)
case _ => list
}
}
val stop : Int = math.sqrt(maxNum).toInt
sieve((2 to maxNum).toList, stop)
}
def main(args: Array[String]) = {
val ap = printf("%d ", (_:Int));
// works
getPrimes(1000).foreach(ap(_))
// works
getPrimes(100000).foreach(ap(_))
// out of memory
getPrimes(1000000).foreach(ap(_))
}
}不幸的是，当我想要计算所有小于1000000 (100万)的质数时，它会失败。我正在接收OutOfMemory。
你对如何优化代码有什么想法，或者我如何以一种更优雅的方式实现这个算法。
PS:我在Haskell中做过类似的事情，在那里我没有遇到任何问题。
回答 5
Stack Overflow用户
发布于 2011-01-05 03:43:52
我会选择无限流。使用惰性数据结构可以编写与Haskell非常相似的代码。它自动读起来比你写的代码更具“声明性”。
import Stream._
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 getPrimes(maxNum : Int) = primes.takeWhile(_ < maxNum)显然，这不是性能最好的方法。阅读The Genuine Sieve of Eratosthenes可以获得一个很好的解释(它是Haskell，但不是太难)。对于很大的范围，你应该考虑Sieve of Atkin。
Stack Overflow用户
发布于 2011-01-05 01:54:23
有问题的代码不是尾递归，所以Scala不能优化递归。此外，Haskell在默认情况下是非严格的，所以您很难将其与Scala进行比较。例如，Haskell受益于foldRight，Scala受益于foldLeft。
有许多Eratosthenes的Sieve的Scala实现，包括一些在Stack Overflow中。例如：
(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))Stack Overflow用户
发布于 2014-12-07 18:06:24
下面的答案大约比"one-liner" answer using a Set快100倍(并且结果不需要按升序排序)，而且比the other answer using an array更像是一个函数形式，尽管它使用可变的BitSet作为筛选数组：
object SoE {
def makeSoE_Primes(top: Int): Iterator[Int] = {
val topndx = (top - 3) / 2
val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
def cullp(i: Int) = {
import scala.annotation.tailrec; val p = i + i + 3
@tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
cull((p * p - 3) >>> 1)
}
(0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
}
}可以通过以下代码进行测试：
object Main extends App {
import SoE._
val top_num = 10000000
val strt = System.nanoTime()
val count = makeSoE_Primes(top_num).size
val end = System.nanoTime()
println(s"Successfully completed without errors. [total ${(end - strt) / 1000000} ms]")
println(f"Found $count primes up to $top_num" + ".")
println("Using one large mutable1 BitSet and functional code.")
}上面的结果如下：
Successfully completed without errors. [total 294 ms]
Found 664579 primes up to 10000000.
Using one large mutable BitSet and functional code.即使对于较小的筛选范围，也有大约40毫秒的开销，并且随着BitSet的大小超过不同的CPU缓存，会有各种非线性响应随着范围的增加而增加。
https://stackoverflow.com/questions/4595941
复制相似问题
腾讯云开发者
