On 2/24/12 3:40 AM, Christoph Breitkopf wrote:
On Fri, Feb 24, 2012 at 4:48 AM, wren ng thorntonw...@freegeek.org 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,
Evan Laforge qdun...@gmail.com 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
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
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 w...@freegeek.org wrote:
When the two maps are of vastly
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
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
Hello,
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
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 ],
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 w...@freegeek.orgwrote:
On 2/23/12 9:16 PM, Clark Gaebel
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
10 matches
Mail list logo
