似乎优化的原始检查变化在Haskell中变成了悲观

Question

我编写了两个函数来检查Haskell中的数字是否为素数:

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

第一个版本平均应该是第二个版本的计算的一半,因为偶数数字被跳过,但事实证明第二个版本看起来更慢几乎快2倍!我逐字包括终端会话时间.

Prime 1版本:

$ 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

现在我使用更改程序来使用prime2版本:

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

代码main简单地说是:

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

如果它的两倍于modolus,为什么第二个版本会更快？

Answer 1

正如丹尼尔在评论中指出的那样，询问会像第二个版本一样even n进行操作。mod此外，这将是第二版本中的第一个案例。所以第二个版本的 case 分支较少，但效率相同。请记住，Haskell 是一种非严格语言，因此mod如果第一个操作已经返回，则所有其他操作都不会被强制True。