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
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