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. On Thu, Feb 23, 2012 at 10:13 PM, wren ng thornton wrote:

On 2/23/12 9:16 PM, Clark Gaebel wrote:

...

Looking at IntMap's left-biased 'union' function [1], I noticed that the complexity is O(n+m) where n is the size of the left map, and m is the size of the right map.

Since insertion [2] is O(min(n, W)) [ where W is the number of bits in an Int ], wouldn't it be more efficient to just fold 'insert' over one of the lists for a complexity of O(m*min(n, W))? This would degrade into O(m) in the worst case, as opposed to the current O(n+m).

The important things to bear in mind here are (1) the constant factors actually matter in practice, and (2) what's actually going on. While O(min(n,W)) is correct, it's incorrect to think about it as just a constant (or as just a linear function). While technically incorrect, it's better to think of it as O(log n) in order to get an intuition for how it works. And O(m+n) is much nicer than O(m*log n).

Doing a fold with insert means that we must pay for the cost of traversing one of the maps entirely, and the cost of walking the spine for a lookup/insert m times. Whereas, with the merge function we only have to traverse the portions of the spines which intersect, and we only have to do it in one pass. In doing the fold, we're essentially ignoring the fact that the maps have a trie structure, since we have to traverse from the top for every insert; whereas for the merge, we make use of the structure in order to avoid redundant traversals of the top part of the structure.

Thus, the merge is doing less work. So, in theory, it should be faster. However, again, the thing to beware of is the constant factors. In particular, big-O algorithmic analysis doesn't really account for things like locality and cache coherence, so one should always be on the lookout for places where duplicating work is actually faster in practice. If you're curious, you can always implement your own union using the fold-with-insert method and then run some benchmarks.

-- Live well, ~wren

______________________________**_________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe

Folding insert might still be a win if one of the maps is very much smaller than the other, but since size is O(n) for Data.IntMap, there's no way to find out if that's the case. - chris On Fri, Feb 24, 2012 at 4:48 AM, wren ng thornton wrote:

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.

Evan Laforge wrote:

I've wondered if it's faster to insert many keys by successive insertion, or by building another map and then unioning, and likewise with deletion. I eventually decided on successive, thinking a log n build + merge is going to be slower than a m*log n for successive insertion. So I wound up with:

If you don't already have the keys in a map, I don't think you gain much by building a map and then merging rather than just inserting them directly. It will produce extra garbage (unless you have some interest in the map you're building), and you have to make the same spine traversals in building the map as you would have inserting into the larger map (and then you have to traverse the larger map during merging). But again, thanks to Criterion, benchmarking is cheap and easy. No need to believe in the folklore or opinions of others :) Though, if the set of keys to be added is very large, then the build+merge approach would allow you to parallelize the building of the map (split the key set in "half" and build maps for each set, recursing as necessary; then either merge the new maps together before merging with the target map, or just merge them with the target map in serial). -- Live well, ~wren

I've wondered if it's faster to insert many keys by successive insertion, or by building another map and then unioning, and likewise with deletion. I eventually decided on successive, thinking a log n build + merge is going to be slower than a m*log n for successive insertion. So I wound up with: insert_list :: (Ord k) => [(k, v)] -> Map.Map k v -> Map.Map k v insert_list kvs m = List.foldl' (\m (k, v) -> Map.insert k v m) m kvs delete_keys :: (Ord k) => [k] -> Map.Map k a -> Map.Map k a delete_keys keys fm = Map.difference fm (Map.fromList [(k, ()) | k <- keys]) Oops, I guess I changed my mind by the time I got to writing 'delete_keys' :) But if the list of things to insert or delete is already sorted, then you could take advantage of fromListAsc and maybe a union would save some time? On Fri, Feb 24, 2012 at 12:38 AM, Serguey Zefirov wrote:

2012/2/24 Clark Gaebel :

...

Since insertion [2] is O(min(n, W)) [ where W is the number of bits in an Int ], wouldn't it be more efficient to just fold 'insert' over one of the lists for a complexity of O(m*min(n, W))? This would degrade into O(m) in the worst case, as opposed to the current O(n+m).

Or am I just crazy?

This way you will create much more garbage, I think. The union of two completely disjoint maps can hold parts of them intact.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe