CODEWITHSUNDEEP
haskelloptimization
afkbowflexin
afkbowflexin

Reputation: 4089

Why is this Haskell expression so slow?

I'm working on Project Euler Problem 14. Here's my solution.

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

I'm running the following out of GHCi

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

I know that if Haskell evaluated strictly, the time on this would be something like O(n3). Since Haskell evaluates lazily though, it seems like this should be some constant multiple of n. This has been running for nearly an hour now. Seems very unreasonable. Does anyone have any idea why?

Upvotes: 9

Views: 824

Answers (3)

hammar
hammar

Reputation: 139840

You're assuming that the collatzLength function will be memoized. Haskell does not do automatic memoization. You'll need to do that yourself. Here's an example using the data-memocombinators package.

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]]

This runs in about 1 second when compiled with -O2.

Upvotes: 22

wenlong
wenlong

Reputation: 1434

cL is short for collatzLength

cL!!n stands for collatzLength n

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

Simple test:

ghci> cL !! 13
10

Upvotes: 0

Johannes Weiss
Johannes Weiss

Reputation: 54031

For being able to find a maximum of a list, the whole list needs to be evaluated.

So it will calculate collatzLength from 1 to 1000000 and collatzLength is recursive. The worst thing is, that your definition of collatzLength is even not tail-recursive.

Upvotes: 1

Related Questions