## Map (unlike Set) lacks efficient merge

Expand Messages
• I just finished writing a solution to a programming contest problem from the 2011 ACM world finals. My solution involved maintaining a sequence of lines
Message 1 of 2 , Sep 3, 2011
• 0 Attachment
I just finished writing a solution to a programming contest problem from the 2011 ACM world finals. My solution involved maintaining a sequence of lines ordered by slope. I wanted to use a Map, where the key was the slope and the value was a point (x,y) that the line went through.

At one point the algorithm requires splitting this list at a particular slope, deleting some of the lines neighboring that slope, and then joining the two sorted lists back together.

I was unable to figure out how to do this efficiently using Map.

Let me be more specific. Suppose I create a create sets of integers with:

module Iset = Set.Make (struct type t = int let compare = compare end)

Now if I have two sets a and b, where all the integers in a are less than all the integers in b, I can join them together with:

Iset.union a b

And this runs in O(log n) time where n is the number of elements in a+b. (This fact is not stated in the documentation, but you can derive it from the code in set.ml. It's a beautiful implementation.)

However, there is apparently no way to do this with a Map. You can try to use "merge", but this traverses both of the trees, and runs in O(n) time instead of O(log n) time.

So I solved my problem, in a somewhat cumbersome way, using sets instead of maps. The maps module really ought to support this. So this is not really a question. It's an observation that there's something substantial missing in the maps module.

My solution is here: http://www.cs.cmu.edu/~sleator/work/works.ml
The problems is problem F here: http://cm.baylor.edu/digital/icpc2011.pdf

Danny Sleator
Carnegie Mellon University
• You may be interested in the Batteries library, which provides an additional layer over the standard library, and has in particular an efficient `merge : (key
Message 2 of 2 , Sep 3, 2011
• 0 Attachment
You may be interested in the Batteries library, which provides an additional
layer over the standard library, and has in particular an efficient `merge :
(key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t`
implementation:
http://batteries.forge.ocamlcore.org/

http://ocaml-batteries-team.github.com/batteries-included/hdoc/BatMap.S.html

`merge` can easily express union, and use `split` internally exactly as in
Set. This doesn't take advantage of the special case you described, where
you know that all keys one of the set/map are smaller than the keys in the
other; the underlying functions 'concat' or 'join', present in the
implementation of both Set and Map, provide this capability, but they're not
exposed through the public interface, probably because the invariant
deferred to the user is quite constraining (and a potential source of bugs),
while the same asymptotic performances are retained by the more general
`merge` or `union` functions.

On Sun, Sep 4, 2011 at 12:50 AM, darooha <sleator@...> wrote:

> I just finished writing a solution to a programming contest problem from
> the 2011 ACM world finals. My solution involved maintaining a sequence of
> lines ordered by slope. I wanted to use a Map, where the key was the slope
> and the value was a point (x,y) that the line went through.
>
> At one point the algorithm requires splitting this list at a particular
> slope, deleting some of the lines neighboring that slope, and then joining
> the two sorted lists back together.
>
> I was unable to figure out how to do this efficiently using Map.
>
> Let me be more specific. Suppose I create a create sets of integers with:
>
> module Iset = Set.Make (struct type t = int let compare = compare end)
>
> Now if I have two sets a and b, where all the integers in a are less than
> all the integers in b, I can join them together with:
>
> Iset.union a b
>
> And this runs in O(log n) time where n is the number of elements in a+b.
> (This fact is not stated in the documentation, but you can derive it from
> the code in set.ml. It's a beautiful implementation.)
>
> However, there is apparently no way to do this with a Map. You can try to
> use "merge", but this traverses both of the trees, and runs in O(n) time
> instead of O(log n) time.
>
> So I solved my problem, in a somewhat cumbersome way, using sets instead of
> maps. The maps module really ought to support this. So this is not really
> a question. It's an observation that there's something substantial missing
> in the maps module.
>
> My solution is here: http://www.cs.cmu.edu/~sleator/work/works.ml
> The problems is problem F here: http://cm.baylor.edu/digital/icpc2011.pdf
>
> Danny Sleator
> Carnegie Mellon University
>
>
>
>
>
>
>
>
> ------------------------------------
>