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.
Haskell-Cafe mailing list