上斯卡拉性能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

回答

相關問題