[Haskell-cafe] Data.IntMap union complexity
wren ng thornton
wren at freegeek.org
Fri Feb 24 04:48:50 CET 2012
On 2/23/12 10:22 PM, Clark Gaebel wrote:
> The situation I encounted this is doing a batch update of a map. Is there
> an easy way to do that? I'm doing something like adding 20-or-so elements
> to an existing map of a few thousand.
The O(m+n) of the merging functions is actually on the order of the size
of the spine intersection between the two maps. Thus, it only ever
approaches that limit in cases where the maps are of approximately equal
size and are designed for the spines to clash in the worst way. An
example would be if you're merging the set of all even numbers and the
set of all odd numbers; you have to traverse the whole tree up to the
last bit. Ditto for taking the union of a set with itself.
When the two maps are of vastly different sizes, O(min(m,n)) is a more
intuitive way to think about it. Since you only have to look at the
places where the spines clash, that will be on the order of the smaller map.
More information about the Haskell-Cafe