我正在 Haskell 中嘗試不同的主要測驗人員。該演算法通過嘗試將整數 n 除以從 2 到sqrt(n)的每個整數i來檢查整數n是否為素數：
isPrime2a n =
helper 2
where
helper i
| (i * i) > n = True
| mod n i == 0 = False
| otherwise = helper (i 1)
我相信這個實作只測驗素數除數：
primes3a = 2 : 3 : filter isPrime3a [4..]
isPrime3a n =
not (divisibleByAny (tail primes3a))
where
divisibleByAny (i : rest)
| (i * i) > n = False
| mod n i == 0 = True
| otherwise = divisibleByAny rest
這個成績單表明（與我的預期相反）第一個函式更快：
ghci> isPrime2a 10000000019
True
(0.14 secs, 50,455,088 bytes)
ghci> isPrime3a 10000000019
True
(1.27 secs, 475,058,704 bytes)
怎么會？我對演算法的分析是否不正確，或者構建串列的開銷是否超過了減少的mod運算元量？
uj5u.com熱心網友回復：
這不僅僅是記憶。
逐步了解這對于一個相當小的數字是如何作業的，比如 29。
isPrime2a必須將 29 除以 2，然后除以 3，再除以 4，再除以 5，然后它停在 6（因為 6*6 = 36，大于 29）并報告True.
isPrime3a必須將 29 除以 2，然后除以 3，然后除以的下一個元素primes3a。要計算出它filter isPrime3a [4..]必須將 4 除以 2 以確認下一個元素不是 4。然后filter isPrime3a必須將 5 除以 2，然后在 3 處停止以確認 5是的下一個元素primes3a。
那么 thenisPrime3a可以將 29 除以 5，然后我們回到需要 的下一個元素primes3a，這意味著運行filter isPrime3a更多。我們最多為 6，所以我們將 6除以2 以發現它不是primes3a. 然后filter isPrime3a考慮 7，這意味著將其除以 2，然后除以 3，然后停在 5（4 不在 中primes3a，記住）以確認 7在中primes3a。
終于isPrime3a可以停止了，因為 7*7 = 49，也就是 > 29。
那是更多的步驟！請注意，isPrime3a只需將 29 除以 2、3 和 5，而isPrime2a必須將 29 除以 2、3、4、5 和 6；isPrime3a必須跳過 4 和 6，節省 2 個師。但要做到這一點，它必須將 4 除以 2、5 除以 2 和 3、6 除以 2 以及 7 除以 2 和 3；為了拯救這 2 個師，我們做了另外 6 個師！還有一些管理開銷，not就像filter在primes2a.
但是，當我們多次運行它們時，我們會看到不同的行為：
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.06 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
請注意，重復執行需要相同的時間（和記憶體）。
λ isPrime3a 10000000019
True
it :: Bool
(0.68 secs, 475,082,944 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.01 secs, 4,198,032 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.01 secs, 4,198,032 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.02 secs, 4,198,032 bytes)
isPrime3a takes much more time and memory than isPrime2a on the first execution. Subsequent ones are much faster and allocate less; the primes3a list has already been built, so although it's occupying a good chunk of memory it doesn't have to be built for any following isPrime3a query (that doesn't need any more primes).
Also, you have a bug in your implementation.
λ take 20 primes3a
[2,3,4,5,6,7,8,10,11,13,14,17,19,22,23,26,29,31,34,37]
it :: [Integer]
Because you check not (divisibleByAny (tail primes3a)), you never check for divisibility by the head of primes3a, namely 2. Thus all even numbers are reported as primes. Fixing that:
λ isPrime3a' 10000000019
True
it :: Bool
(0.33 secs, 230,822,560 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
Doesn't change the conclusion really. It's still much slower than isPrimes2 on the first execution, much faster on subsequent runs.
Long story short: both of these behaviours are useful. If you needed to test primality in a real program and had to choose between these two implementations, you might go for primes2a if you only needed to test one (or a handful) of numbers. primes3a looks good if you're going to test lots of numbers, and you can afford to keep a large list in memory the whole time (or you're testing numbers small enough that the list isn't large). Neither one isn't strictly better than the other, on these numbers.
Of course, as Louis Wasserman pointed out in the comments, serious performance measurement (i.e. meaningful to help you predict the performance of programs as they would be run for practical purposes) should not be made in GHCi. How to do it properly is a whole other topic, but the biggest thing you're missing is that the code is not optimised, and GHC's optimizer can make a huge difference to the speed and execution of code, but it is also very non-uniform in how much it speeds things up. It's very possible that you can have two versions of an algorithm where one is more than 10 times faster than the other when you compare an unoptimised build while the reverse is true when you compare optimised build. If you care about the performance then you'll almost always going to run it with optimisation, so that's usually the state you want to measure.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/434056.html
上一篇：:~:和:~~:等式有什么區別？
下一篇：錯誤使用簡單的Haskell函式