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

12922Re: "ocaml_beginners"::[] Map (unlike Set) lacks efficient merge

Expand Messages
  • Gabriel Scherer
    Sep 3, 2011
      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`


      `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]
    • Show all 2 messages in this topic