[Haskell-cafe] (no subject)

[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