This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Set union
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2005-02-25 (19:46) From: Jon Harrop Subject: Re: [Caml-list] Complexity of Set.union
```On Friday 25 February 2005 17:48, Xavier Leroy wrote:
> My hope is that union takes time O(N log N) where N is the sum of the
> numbers of elements in the two sets.  I'm thoroughly unable to prove
> that, though, in particular because the complexity of the "split"
> operation is unclear to me.

Am I correct in thinking that your derivation of this assumes roughly
equal-sized sets and that your complexity could be tightened a bit by using
the two different set cardinalities explicitly?

I ask this because the STL set_union is probably O(n+N) (inserting an already
sorted range into a set is apparently linear) which is worse than the O((n+N)
log(n+N)) which you've suggested for OCaml.

But my OCaml code is vastly faster, so OCaml's complexity seems to be
significantly better than that. At least in the special case of one small and
one large set, which my code is bound by. Specifically, the sets have O(1)
and O(i^2) elements when looking for the "i"th nearest neighbour. In reality
this corresponds to computing the unions of sets containing 4 elements with
sets containing 10^4 elements.

Hmm, now that I come to think of it, my performance measurements have all been
specific to silicon (that's where the 4 comes from). I'll try retiming on
some other atomic structures, where the small sets will contain about 12
elements. I predict the OCaml code will do better relative to the C++ code,
because the smaller sets won't be so small...

> This bound is "reasonable", however, in that the trivial union
> algorithm (repeatedly add every element of one of the sets to the
> other one) achieves this bound, and the trick with "joining" is,
> intuitively, just an optimization of this trivial algorithm.

I see. This could be improved in the unsymmetric case, by adding elements from
the smaller set to the larger set. But the size of the set isn't stored so
you'd have to make do with adding elements from the shallower set to the
deeper set. I've no idea what the complexity of that would be...

As I know which of the two sets will be the larger and which will be the
smaller, I'll try a customized union function which folds Set.add over the
smaller set.

> > Now, what about best case behaviour: In the case of the union of two
> > equal height, distinct sets, is OCaml's union T(1)?
>
> Did you mean "of two equal height sets such that all elements of the
> first set are smaller than all elements of the second set"?

Yes, that's what I meant. :-)

> That
> could indeed run in constant time (just join the two sets with a
> "Node" constructor), but I doubt the current implementation achieves
> this because of the repeated splitting.

Having said that, wouldn't it take the Set.union function O(log n + log N)
time to prove that the inputs are non-overlapping, because it would have to
traverse to the min/max elements of both sets?

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://ffconsultancy.com

```