[Haskell-cafe] Data.IntMap union complexity

[Evan Laforge]

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 <sergueyz at gmail.com> wrote:
> 2012/2/24 Clark Gaebel <cgaebel at csclub.uwaterloo.ca>:
>> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe