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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
