[Haskell-cafe] (no subject)
wren ng thornton
wren at freegeek.org
Thu Oct 15 02:11:57 EDT 2009
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)
Whereas Data.Map is O(log n) for the usual balanced tree approach.
More information about the Haskell-Cafe