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

[Bruno Carnazzi]

2008/4/1, Chaddaï Fouché <chaddai.fouche at gmail.com>:
> 2008/3/31, Bruno Carnazzi <bcarnazzi at gmail.com>:
>
> >    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.