There are also the judy arrays http://hackage.haskell.org/package/HsJudy http://hackage.haskell.org/package/judy
dons recently advertised the latter as being 2x faster than IntMap, but I don't know in what respect these two packages differ and why Don decided to create 'judy' despite the existence of HsJudy. 2009/10/15 wren ng thornton <w...@freegeek.org>: > Jake McArthur wrote: >> >> staafmeister wrote: >>> >>> Yes I know but there are a lot of problems requiring O(1) array updates >>> so then you are stuck with IO again >> >> Or use ST. Or use IntMap (which is O(log n), but n is going to max out on >> the integer size for your architecture, so it's really just O(32) or O(64), >> which is really just constant time). > > Actually, IntMap is O(min(n,W)) where W is the number of bits in an Int. > Yes, IntMaps are linear time in the worst case (until they become > constant-time). In practice this is competitive with all those O(log n) > structures though. > > Whereas Data.Map is O(log n) for the usual balanced tree approach. > > -- > Live well, > ~wren > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe