performance - 在 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 倍!我逐字包括终端 session 时间。

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]

如果第二个版本是模数的两倍，为什么它会更快？

Answer 1

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