Re: [Caml-list] Complexity of Set.union

[Jon Harrop <jon@jdh30.plus.com>]

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