Loading ...
Sorry, an error occurred while loading the content.

12921Map (unlike Set) lacks efficient merge

Expand Messages
  • darooha
    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
    • Show all 2 messages in this topic