[Haskell-cafe] [Newbie] Problem with Data.Map (or something else
?)
Don Stewart
dons at galois.com
Tue Apr 1 00:45:40 EDT 2008
chaddai.fouche:
> 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 ?
>
> > 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
>
> 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.
>
and if its got Int indices, Data.IntMap is always a better option than Data.Map
and usually outperforms the HashTable type, while being pure.
More information about the Haskell-Cafe
mailing list