समेकित फ़ंक्शन बहुत धीमा है

Question

मैंने लिखा हैप्रिम फ़ंक्शन। यह जांचता है कि दिया गया नंबर प्राइम है या नहीं। अंतिम "प्राइम" सूची अलग से दी जाती है।

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 

मैंने सोचा कि यह हमेशा से एक में दो कार्यों को मजबूत करने की बेहतर था अगर possible..so मैं एक समारोह isPrime2 में isPrime और प्रधानमंत्री को समेकित किया। लेकिन isPrime2 का प्रदर्शन बहुत खराब है।

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 सेकंड

isPrime2 40000000000000000001

=> 19.8 सेकंड

मेरे मशीन उबंटू 17.10 x86-64 है। मैं ghc 8.2.1 का उपयोग कर रहा हूँ। क्या किसी को पता है क्यों?

Answer 1

पहला स्निपेट स्मृति में prime एस की केवल एक सूची रखेगा।

दूसरा टुकड़ा अपने स्वयं के prime तक n^2हर बारisPrime2 कहा जाता है की गणना करेगा। पहले खोजे गए प्राइम्स को हर कॉल पर खरोंच से हटा दिया जाता है और फिर से दबाया जाता है। चूंकि isPrime2 रिकर्सिव है यह एक झटका लग जाता है।

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 

यह isPrime2 के हर कॉल पर prime recompute जाएगा, लेकिन भीतरी isPrime से प्रत्येक कॉल के बाद एक झटका-अप करने के लिए नेतृत्व एक ही सूची का उपयोग करेंगे नहीं होगा:

एक मध्यवर्ती दृष्टिकोण यह एक हो सकता है prime एस।