2008/4/1, Bruno Carnazzi
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ï