2008/4/1, Chaddaï Fouché <[EMAIL PROTECTED]>: > 2008/3/31, Bruno Carnazzi <[EMAIL PROTECTED]>: > > > 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
