Set union
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050225 (19:46) 
From:  Jon Harrop <jon@j...> 
Subject:  Re: [Camllist] 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 equalsized 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 nonoverlapping, 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