使用Haskell進行Prime測試的性能

我有兩種測試素數的方法。其中一個叫isPrime，另一個叫isBigPrime。我最初想要的是用我已經計算過的「小」素數來測試「大」素數，以便測試變得更快。下面是我的實現：使用Haskell進行Prime測試的性能

intSqrt :: Integer -> Integer 
intSqrt n = round $ sqrt $ fromIntegral n 

isPrime' :: Integer->Integer -> Bool 
isPrime' 1 m = False 
isPrime' n m = do 
    if (m > (intSqrt n)) 
    then True 
    else if (rem n (m+1) == 0) 
     then False 
     else do isPrime' n (m+1) 

isPrime :: Integer -> Bool 
isPrime 2 = True 
isPrime 3 = True 
isPrime n = isPrime' n 1 
isBigPrime' :: Integer ->Int ->Bool 
isBigPrime' n i = 
    if ((smallPrimes !! i) > intSqrt n) 
    then True 
    else if (rem n (smallPrimes !! i) == 0) 
     then False 
     else do isBigPrime' n (i+1) 
smallPrimes = [2,3, List of Primes until 1700] 
--Start at 1 because we only go through uneven numbers 
isBigPrime n = isBigPrime' n 1 
primes m = [2]++[k | k <- [3,5..m], isPrime k] 
bigPrimes m = smallPrimes ++ [k | k <- [1701,1703..m], isBigPrime k] 
main = do 
    print $ (sum $ [Enter Method] 2999999)

我選擇了1700作爲上限，因爲我想有質數多達3E6和開方（3E6）〜1700年我把他們的總和這兩種算法進行比較。我認爲bigPrimes會更快，primes，因爲首先它不會計算和它有一個開始，這不是太大，但無論如何。但令我驚訝的是bigPrimes比primes慢。下面是結果：

對於primes

Performance counter stats for './p10': 


     16768,627686  task-clock (msec)   # 1,000 CPUs utilized   
       58  context-switches   # 0,003 K/sec     
       1  cpu-migrations   # 0,000 K/sec     
      6.496  page-faults    # 0,387 K/sec     
    53.416.641.157  cycles     # 3,186 GHz      
    <not supported>  stalled-cycles-frontend 
    <not supported>  stalled-cycles-backend 
    160.411.056.099  instructions    # 3,00 insns per cycle   
    34.512.352.987  branches     # 2058,150 M/sec     
     10.673.742  branch-misses    # 0,03% of all branches   

     16,773316435 seconds time elapsed

和bigPrimes

Performance counter stats for './p10': 

     19111,667046  task-clock (msec)   # 0,999 CPUs utilized   
       259  context-switches   # 0,014 K/sec     
       3  cpu-migrations   # 0,000 K/sec     
      6.278  page-faults    # 0,328 K/sec     
    61.027.453.425  cycles     # 3,193 GHz      
    <not supported>  stalled-cycles-frontend 
    <not supported>  stalled-cycles-backend 
    198.207.905.034  instructions    # 3,25 insns per cycle   
    34.632.138.061  branches     # 1812,094 M/sec     
     106.102.114  branch-misses    # 0,31% of all branches   

     19,126843560 seconds time elapsed

我想知道爲什麼會出現這種情況。我懷疑使用primes!!n使bigPrimes稍慢，但我不完全確定。

來源

2017-03-16 Gonenc Mogol

從查看你的統計數據來看，跳出來的最大差異是'''branch-missses'''。你對小素數的函數有'''10.673.742分支未命中＃0,03％所有分支''和你的大素數函數有'''106.102.114分支未命中＃0,31％所有分支'''。你的大素數函數誤預測分支10倍和你的小素數函數一樣多。這可能會導致一些放緩。儘管如此，即使對於大質數來說，缺失率也足夠小，因此它可能不是整個故事 – Rainbacon

如果您只是想檢查某個特定數字是否爲素數，那麼有更好的方法。查看Rabin-Miller，例如 – user2297560

「p大於n的平方根」相當於「p的平方大於n」，然而，後者只需要整數乘法和比較，而前一個需要更多的CPU工作。 – Ingo

從其他語言帶來的常見反模式是遍歷索引並使用(!!)索引到列表中。在Haskell中，它只是迭代列表本身而已。所以：

isBigPrime' :: Integer -> [Integer] ->Bool 
isBigPrime' n [] = True 
isBigPrime' n (p:ps) = p > intSqrt n || (rem n p /= 0 && isBigPrime' n ps) 

isBigPrime n = isBigPrime' n (drop 1 smallPrimes)

在我的機器，你primes需要25.3s;你的bigPrimes需要20.9秒;而我的bigPrimes需要3.2s。還有其他一些低懸的成果（例如使用p*p > n而不是p > intSqrt n），但這是迄今爲止最重要的一個。

來源

2017-03-16 19:49:49

非常整齊！這應該改變我的Haskell編程方式。我還是新手。雖然我想知道爲什麼'!!'這麼慢。 –

@gonenc'（!!）'很慢，因爲它是一個無用的O（n）索引操作進入鏈表。 –

使用Haskell進行Prime測試的性能

回答

相關問題