上斯卡拉性能tunning

我是新来的Scala问题，只是写了这个程序：上斯卡拉性能tunning

def isPrime(num: Int, primes: scala.collection.mutable.MutableList[Int]): Boolean = { 
    primes.takeWhile(i => i * i <= num).forall(num % _ > 0) 
} 
//def isPrime(num: Int, primes: scala.collection.mutable.MutableList[Int]): Boolean = { 
// !primes.forall(num%_!=0) 
//} 


def primeListUnder(upper: Int) = { 
    val primes=scala.collection.mutable.MutableList(2,3); 
    var num=4 
    while(num<upper) { 
    if(isPrime(num,primes)) 
    { 
     primes+=num 
    } 
    num+=1 
    } 
    primes 
}

这是试图获得在某些特定上限的所有质数。但它运行速度非常慢。有什么建议吗？

加入：其实我的观点是要知道为什么这个程序运行得如此缓慢。这不是关于如何计算素数。

编辑：更改isPrime方法以首先过滤出一些数字（数学）。现在运行得更快，我的Mac上需要大约10秒才能算到2000000;

来源

2014-10-31 Stanley Shi

检查这个http://stackoverflow.com/questions/9711785/find-prime-numbers-using-scala-help-me-to-improve/13202109#13202109 – 2014-10-31 09:45:40

你说什么运行“你真的很慢“？有更快的方法，但你的方法似乎并不合理 – 2014-10-31 11:08:05

花费10秒钟，发现200万的质数是缓慢的，因为使用Eratosthenes的一个简单的基本Sieve只需要几十个毫秒的微不足道的任务。部分原因是模数（“％”）操作所隐含的分割是现代CPU在每秒钟10个CPU时钟周期内执行的最慢基元整数操作之一，而添加通常需要CPU时钟周期的一小部分，而即使乘法只需要大约一个时钟周期。 Eratosthenes的Sieve使用简单的基本操作执行所有内循环操作，每个循环只有几个时钟。 – GordonBGood 2015-04-02 06:48:18

要列出所有的素数少于特定的数字，你应该使用Eratosthenes筛。它比你的算法快得多。

你的算法是如此之慢becouse它检查每数量与所有素数不到它，直到它找到它的除数。所以每个数字都会至少检查一个素数。但是，当检查数字增长时，素数列表会增加，可能的检查数量会增加。

经过多次检查后会有数字被拒绝。例如，在检查2,3,5,7,11,13后，第26位将被拒绝。

此外，在检查全部减去素数后，将接受每个素数。

与您的算法相比，Eratosthenes算法筛将其标记为'素数'或'不是素数'后会触及每个数字。

来源

2014-10-31 09:34:55 rtruszk

谢谢！但就我的理解而言，“forall”方法一旦不符合预测就会退出，对吗？然后是“素数。forall“将退出第一个数字”num％_ == 0“ – 2014-10-31 09:54:59

@StanleyShi，虽然您的程序只会检查直到它找到均匀分割的除数，但每找到一个数字都需要测试它（每个已发现的素数达到其平方根，因此，平均而言，每个发现素数所做的工作量平均增加得越快，检查素数的数量范围就越高，这与其他算法前面提到的Eratosthenes筛选中，每增加一个范围，每个找到的素数的工作量就会非常缓慢地增加。 – GordonBGood 2015-04-02 06:40:18

正如@rtruszk提到，从my answer on the other linked question转贴的埃拉托色尼的真实筛（SOE）下面的代码会跑的比你的代码快得多较大范围：

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 } 
    } 
}

上面的代码的大部分（使用尾递归或高阶函数以及不同于用于快速筛选合成数字的BitSet数组的内容的不变性）。它不如使用Java.util.BitSet快，但生成的代码稍微优雅。

来源

2014-12-07 11:23:40 GordonBGood

上斯卡拉性能tunning

回答

相关问题