यह हास्केल अभिव्यक्ति इतनी धीमी क्यों है?

Question

मैं प्रोजेक्ट यूलर समस्या 14 पर काम कर रहा हूं। यह मेरा समाधान है।

import Data.List 

collatzLength :: Int->Int 
collatzLength 1 = 1 
collatzLength n | odd n = 1 + collatzLength (3 * n + 1) 
       | even n = 1 + collatzLength (n `quot` 2) 

maxTuple :: (Int, Int)->(Int, Int)->Ordering 
maxTuple (x1, x2) (y1, y2) | x1 > y1 = GT 
       | x1 < y1 = LT 
       | otherwise = EQ 

मैं निम्नलिखित चल रहा हूँ GHCi

की

maximumBy maxTuple [(collatzLength x, x) | x <- [1..1000000]] 

मुझे पता है कि अगर हास्केल सख्ती से मूल्यांकन किया है, इस पर समय O (n) की तरह कुछ होगा बाहर। चूंकि हास्केल आलसी मूल्यांकन करता है, ऐसा लगता है कि यह एन के कुछ निरंतर एकाधिक होना चाहिए। यह लगभग एक घंटे के लिए चल रहा है। बहुत अनुचित लगता है। क्या किसी को कोई विचार है क्यों?

Answer 1

आप मान रहे हैं कि collatzLength फ़ंक्शन को याद किया जाएगा। हास्केल स्वचालित ज्ञापन नहीं करता है। आपको खुद ऐसा करने की आवश्यकता होगी। data-memocombinators पैकेज का उपयोग कर एक उदाहरण यहां दिया गया है।

import Data.List 
import Data.Ord 
import qualified Data.MemoCombinators as Memo 

collatzLength :: Integer -> Integer 
collatzLength = Memo.arrayRange (1,1000000) collatzLength' 
    where 
    collatzLength' 1 = 1 
    collatzLength' n | odd n = 1 + collatzLength (3 * n + 1) 
        | even n = 1 + collatzLength (n `quot` 2) 

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]] 

यह -O2 के साथ संकलित होने पर लगभग 1 सेकंड में चलता है।

Answer 2

अधिकतम सूची खोजने में सक्षम होने के लिए, संपूर्ण सूची का मूल्यांकन करने की आवश्यकता है।

तो 1 से 1000000 और collatzLength से collatzLength की गणना की जाएगी collatzLength रिकर्सिव है। सबसे बुरी बात यह है कि collatzLength की आपकी परिभाषा पूंछ-पुनरावर्ती भी नहीं है।

Answer 3

cL के लिए collatzLength

cL!!n खड़ा के लिए कम है collatzLength n

cL :: [Int] 
cL = 1 : 1 : [ 1 + (if odd n then cL!!(3*n+1) else cL!!(n `div` 2)) | n <- [2..]] 

सरल टेस्ट:

ghci> cL !! 13 
10