[Haskell-cafe] uvector package appendU: memory leak?
wren ng thornton
wren at freegeek.org
Tue Mar 31 23:09:29 EDT 2009
Manlio Perillo wrote:
> By the way, about insertWith/alter; from IntMap documentation:
> insertWithKey: O(min(n,W)
> alter: O(log n)
> So, alter is more efficient than insertWithKey?
> And what is that `W` ?
As Claus says it's the maximum (value of Int; number of keys). It's in
an easily overlooked comment at the top of the IntMap page, last I checked.
As for which is faster, it depends. The O(min(n,W)) stuff is effectively
linear because n can't exceed W (what would you use for the key?), but
it's a smart linear that rivals O(log n). Because the values of n are so
small, what really matters here are the constant factors not the
asymptotic complexity. Also it depends a lot on what operations you
If you're interested in the details, I highly recommend Okasaki&Gill's
paper where they introduce IntMap. It's eminently readable and gives
comparative numbers to other datastructures for all the basic operations.
More information about the Haskell-Cafe