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

[Chaddaï Fouché]

2008/4/1, Bruno Carnazzi <bcarnazzi at gmail.com>:
> Because I don't know anything about arrays in Haskell. Thank you for
>  pointing this, I have to read some more Haskell manuals :)

A good place to learn about Haskell's array (which come in many
flavours) is this wiki page :
http://www.haskell.org/haskellwiki/Modern_array_libraries

>  >
>  >  > 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 x = if x' <= n then 1 + a ! x' else 1 + syr 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 ?)

Array or Map isn't really the problem here (my algorithm with a Map
instead only take 6s to find the solution) as I thought at first.
The main problem in your code I think is that because of Map.map, you
create multiple copies of your smaller Maps in memory and union force
them to materialize, while the fact that you don't evaluate the value
means the GC won't collect them. Anyway, your algorithm by itself is
pretty slow I think, since for every step to a number which is not
already recorded you must add 1 to all the numbers you passed on the
way.

-- 
Jedaï