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

Map (unlike Set) lacks efficient merge

Expand Messages
  • darooha
    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
    • Gabriel Scherer
      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
        >
        >
        >
        >
        >
        >
        >
        >
        > ------------------------------------
        >
        > Archives up to December 31, 2010 are also downloadable at
        > http://www.connettivo.net/cntprojects/ocaml_beginners
        > The archives of the very official ocaml list (the seniors' one) can be
        > found at http://caml.inria.fr
        > Attachments are banned and you're asked to be polite, avoid flames
        > etc.Yahoo! Groups Links
        >
        >
        >
        >


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.