konsolide edilmiş işlev çok yavaş

Question

Yazım isminin fonksiyonu. Verilen bir sayının asal olup olmadığını kontrol eder. Son "ana" liste ayrı ayrı verilir.

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 

Ben birine iki işlevi pekiştirmek her zaman daha iyi olduğunu düşündüm possible..so Bir fonksiyon isPrime2 içine isPrime ve asal konsolide eğer. Ama isPrime2'nin performansı çok kötü.

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

=> 19.8 saniye

Makinem

isPrime2 40000000000000000001

=> 0.5 saniye isPrime Ubuntu 17.10 X86-64 olup. Ghc 8.2.1 kullanıyorum. Nedenini bilen var mı?

Answer 1

İlk parçacık, bellekte yalnızca bir tane prime s listesini saklar.

ikinci pasajıisPrime2 denir kendi primen^2kadar her seferinde hesaplayacak. Önceden keşfedilen primerler atıldı ve her çağrıda sıfırdan yeniden derlendi. isPrime2 tekrardan beri bu bir patlamaya neden olur.

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 

Bu isPrime2 her aramada prime recompute, ancak aynı listeyi paylaşacak iç isPrime her çağrısı beri darbe-up yol açmayacak:

bir ara yaklaşım bu biri olabilir prime s.