2017-10-30 111 views
6

Yazım isminin fonksiyonu. Verilen bir sayının asal olup olmadığını kontrol eder. Son "ana" liste ayrı ayrı verilir. konsolide edilmiş işlev çok yavaş

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ı?

+0

Benim tahminim, 'asal' bir sabit olduğu için, o anılırken, 'isPrime2' bir işlevdir, bu yüzden olmaz. Bu sadece bir tahmin, ancak ... – MathematicalOrchid

+0

Teşekkürler! Açıklaman bana içgörü verdi. – eii0000

+0

@ eii0000 derlediniz mi veya yorumlandı mı test ediyorsunuz? isPrime2 n 'nizi' '('' (\ p -> n' mod' p/= 0) olarak basitleştirirseniz nasıl karşılaştırırsınız. takeWhile ((<= n). (^ 2)) 2 $: [3,5 ..] ''? –

cevap

6

İ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.

+0

harika ... sizin isPrime2 0,5 saniye de .. Teşekkürler! – eii0000

+0

GHC genellikle optimizasyon sırasında 'prime' ve' isPrime'ı en üst seviyeye kaydırmıyor mu? –

+0

@BenjaminHodgson Hayır, GHC her zaman bir optimizasyon olmadığı için muhafazakar. Bu dönüşümün "tam tembellik" dönüşümüne (ya da bununla ilgili) '', '' y x '' yı y = ... '' .... '' haline gelmesine '' izin veriliyor '' denir (ya da). .. '' '' '' '' '' '' '' '' 'bağlı değildir. Semantikler korunur, ancak hangisinin en iyi performansa sahip olduğunu tahmin etmek zordur (IIRC). – chi