[Haskell-cafe] uvector package appendU: memory leak?

[wren ng thornton]

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 
really need.

If you're interested in the details, I highly recommend Okasaki&Gill's 
paper[1] where they introduce IntMap. It's eminently readable and gives 
comparative numbers to other datastructures for all the basic operations.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452

-- 
Live well,
~wren