chức năng hợp nhất chậm hơn nhiều

Question

Tôi đã viết hàm isPrime. Nó kiểm tra nếu một số đã cho là số nguyên tố hay không. Danh sách "nguyên tố" cuối cùng được cung cấp riêng.

prime :: [Integer] 
prime = 2 : filter isPrime [3..] 
isPrime :: Integer -> Bool 
isPrime n | n < 2 = False 
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime 

Tôi nghĩ tốt hơn nên hợp nhất hai hàm thành một nếu có thể..để tôi củng cố isPrime và nhập thành một hàm isPrime2. Nhưng hiệu suất của isPrime2 rất tệ.

isPrime2 :: Integer -> Bool 
isPrime2 n | n < 2 = False 
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..] 

isPrime 40000000000000000001

=> 0,5 giây

isPrime2 40000000000000000001

=> 19,8 giây

máy của tôi là Ubuntu 17.10 x86-64. Tôi đang sử dụng ghc 8.2.1. Có ai biết tại sao không?

Answer 1

Đoạn đầu tiên sẽ chỉ giữ một danh sách prime giây trong bộ nhớ.

Đoạn thứ hai sẽ tính toán prime riêng của mình cho đến n^2mỗi lần gọiisPrime2 được gọi. Các số nguyên tố được phát hiện trước đó bị loại bỏ và được tính toán lại từ đầu ở mọi cuộc gọi. Kể từ isPrime2 là đệ quy điều này dẫn đến một cú đánh.

Một cách tiếp cận trung gian có thể được điều này một:

isPrime2 :: Integer -> Bool 
isPrime2 m = isPrime m 
    where 
    prime :: [Integer] 
    prime = 2 : filter isPrime [3..] 
    isPrime :: Integer -> Bool 
    isPrime n | n < 2 = False 
    isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime 

này sẽ recompute prime tại mỗi cuộc gọi của isPrime2, nhưng sẽ không dẫn đến một đòn-up vì mỗi tiếng gọi của khu vực nội isPrime sẽ chia sẻ cùng một danh sách trong số prime s.