Primality Scheckzahlung, die Optimierung schien sich heraus Pessimierung in Haskell

Question

Ich schrieb zwei Funktionen zu überprüfen, ob eine Zahl in Haskell Primzahl ist:

prime :: Int -> Bool 
prime 0 = False 
prime 1 = False 
prime 2 = True 
prime n | even n = False 
prime n = all (\x -> n `rem` x /= 0) [3,5..intSqrt] 
    where intSqrt = (floor . sqrt . fromIntegral) n 

prime2 :: Int -> Bool 
prime2 0 = False 
prime2 1 = False 
prime2 n = all (\x -> n `rem` x /= 0) [2..intSqrt] 
    where intSqrt = (floor . sqrt . fromIntegral) n 

Die erste Version soll im Durchschnitt tun Hälfte der Berechnungen der der zweite, weil gerade Zahlen übersprungen werden, aber es stellt sich heraus, dass die zweite Version, die langsamer erscheint, fast 2x schneller ist! Ich schließe Terminalsitzungen wörtlich mit ein.

Prime 1 Version:

$ ghc -O2 prime.hs 
[1 of 1] Compiling Main    (prime.hs, prime.o) 
Linking prime ... 
$ time ./prime 
142913828922 

real 0m4.617s 
user 0m4.572s 
sys 0m0.040s 

Jetzt benutze ich das Programm ändern Verwendung der Prime2 Version zu machen:

$ ghc -O2 prime.hs 
[1 of 1] Compiling Main    (prime.hs, prime.o) 
Linking prime ... 
$ time ./prime 
142913828922 

real 0m2.288s 
user 0m2.268s 
sys 0m0.020s 
$ 

Der Code in main ist einfach:

main :: IO() 
main = print $ sum $ filter prime2 [1..2000000] 

Warum ist die zweite Version schneller, wenn sie die doppelte Anzahl an Modolus hat?

Answer 1

Wie Daniel in den Kommentaren darauf hingewiesen hat, würde even n eine Operation mod genau wie in der zweiten Version tun. Außerdem wäre es der erste Fall in der zweiten Version. Die zweite Version hat also weniger Fallzweige, aber dieselbe Effizienz. Denken Sie daran, Haskell ist eine nicht-strikte Sprache, so dass alle anderen mod Operationen nicht erzwungen werden, wenn die erste bereits True zurückgibt.