primality जांच परिवर्तन यह है कि अनुकूलन लग रहा था निकला हास्केल

Question

में pessimization होने के लिए मैं जाँच करने के लिए दो कार्य लिखा है, तो एक नंबर हास्केल में प्रधानमंत्री है:

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 

पहले संस्करण चाहिए, औसत में से आधे से गणना करने दूसरा, क्योंकि यहां तक ​​कि संख्याएं भी छोड़ दी गई हैं, लेकिन यह पता चला है कि धीमा लगता है कि दूसरा संस्करण लगभग 2x तेज है! मैं टर्मिनल सत्र समय verbatim शामिल हैं।

प्रधानमंत्री 1 संस्करण:

$ 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 

अब मैं प्रोग्राम बदल 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 
$ 

main में कोड बस है:

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

दूसरा संस्करण तेजी से क्यों है यदि यह दो बार मॉडोलस की संख्या करता है?

Answer 1

जैसा कि डैनियल ने टिप्पणियों में बताया, even nmod ऑपरेशन दूसरे संस्करण की तरह ही करेगा। इसके अलावा, यह दूसरे संस्करण में पहली बार हिट होगा। तो दूसरे संस्करण में कम केस शाखाएं हैं लेकिन एक ही दक्षता है। याद रखें हास्केल एक गैर-सख्त भाषा है, इसलिए अन्य सभी mod ऑपरेशंस को मजबूर नहीं किया जाएगा यदि पहले से ही True लौटाता है।