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
