12921Map (unlike Set) lacks efficient merge
- Sep 3, 2011I 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
Carnegie Mellon University
- Next post in topic >>