tính nguyên thay đổi séc mà dường như tối ưu hóa hóa ra là pessimization trong Haskell

Question

tôi đã viết hai chức năng để kiểm tra xem một số là số nguyên tố trong 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 

Phiên bản đầu tiên nên, trung bình làm một nửa các tính toán của thứ hai, bởi vì ngay cả những con số được bỏ qua, nhưng nó chỉ ra rằng phiên bản thứ hai có vẻ chậm hơn là gần như 2x nhanh hơn! Tôi bao gồm thời gian phiên của Phiên làm việc đầu cuối đúng nguyên văn.

Thủ 1 phiên bản:

$ 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 

Bây giờ tôi sử dụng thay đổi chương trình để tận dụng các phiên bản 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 
$ 

Các mã trong main chỉ đơn giản là:

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

Tại sao phiên bản thứ hai nhanh hơn nếu nó tăng gấp đôi số lượng modolus?

Answer 1

Như Daniel đã chỉ ra trong nhận xét, yêu cầu even n sẽ thực hiện thao tác mod giống như trong phiên bản thứ hai. Hơn nữa, nó sẽ là trường hợp đầu tiên nhấn trong phiên bản thứ hai. Vì vậy, phiên bản thứ hai có ít nhánh hơn nhưng hiệu quả tương tự. Hãy nhớ Haskell là một ngôn ngữ không nghiêm ngặt, vì vậy tất cả các hoạt động mod khác sẽ không bị ép buộc nếu lần đầu tiên trả về True.