[Haskell-cafe] [Newbie] Problem with Data.Map (or something else
bcarnazzi at gmail.com
Tue Apr 1 13:50:30 EDT 2008
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.
More information about the Haskell-Cafe