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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
