[Haskell-cafe] Profiling help (Warning: Euler spoilers)

Daniel Fischer daniel.is.fischer at web.de
Thu Mar 4 11:19:32 EST 2010


Am Donnerstag 04 März 2010 16:07:51 schrieb Louis Wasserman:
> Actually, looking back, I'm not sure mapM is even the right choice.
> I think foldM would suffice. All we're doing is finding the association
> pair with the minimum key, no?  In this case, foldM would do everything
> we need to...and State.Strict would be pretty good at that.

Yes, it would (much much better than C.M.S.Lazy). And it would be an 
improvement over the original, but not much.

The real problem is that Data.Map isn't well suited for this task. 
Inserting n key -> value associations into an initially empty Map takes 
O(n*log n) time. Since here the keys have a tendency to come in increasing 
order, there are a lot of rebalancings necessary, giving extra bad 
constants on top.

What one wants here is a data structure with O(1) access and update for the 
cache. Enter STUArray. Of course, now comes the difficulty that you don't 
know how large your numbers will become (56991483520, you probably don't 
have enough RAM for such a large array), so you have to choose a cutoff and 
decide what to do when you exceed that. That makes the code more 
convoluted, but a lot faster.



More information about the Haskell-Cafe mailing list