Scala性能筛选
Scala性能筛选
提问于 2011-01-05 00:30:36
现在，我正在尝试学习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中做过类似的事情，在那里我没有遇到任何问题。
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缓存，会有各种非线性响应随着范围的增加而增加。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4595941
复制相关文章
相似问题
腾讯云开发者
