Re: [Haskell-cafe] [Newbie] Problem with Data.Map (or something else ?)

2008/4/1, Chaddaï Fouché :

2008/3/31, Bruno Carnazzi :

...

Dears Haskellers,

As an Haskell newbie, I'm learning Haskell by trying to resolve Euler Project problems (http://projecteuler.net/ ). I'm hanging on problem 14 (Collatz problem).

I've written the following program... Which does not end in a reasonable time :( My algorithm seems ok to me but I see that memory consumption is gigantic... Is this a memory problem with Data.Map ? Or an infinite loop ? (Where ?) In a more general way, how can I troubleshoot these kind of problem ?

Others have pointed potential source of memory leaks, but I must say that using Data.Map for the cache in the first place appear to me as a very bad idea... Data.Map by nature take much more place than necessary. You have an integer index, why not use an array instead ?

Because I don't know anything about arrays in Haskell. Thank you for pointing this, I have to read some more Haskell manuals :)

...

import Data.Array import Data.List import Data.Ord

syrs n = a where a = listArray (1,n) $ 0:[ syr n x | x <- [2..n]] syr n x = if x' <= n then a ! x' else 1 + syr n x' where x' = if even x then x `div` 2 else 3 * x + 1

main = print $ maximumBy (comparing snd) $ assocs $ syrs 1000000

The logic and the complexity in this algorithm is comparable to mine but the performance difference is huge, which is not very intuitive in my mind (There is no "1+1+1+1+1..." problem with array ?)

This solution takes 2 seconds (on my machine) to resolve the problem.

On the other hand, now that I have read your solution, I see that using Map was the least of the problem... All those Map.map, while retaining the original Map... Your solution is too clever (twisted) for its own good, I suggest you aim for simplicity next time.

-- Jedaï

Thank you, Bruno.