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 <sergu...@gmail.com> wrote: > 2012/2/24 Clark Gaebel <cgae...@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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe