Re: set intersection -> true/false

oanacb@xxxxxxxxx wrote:
> i am looking for an algorithm that without calculating/storing the
> result of a set intersection (i have rather large sets...and a lot of
> them) gives just a bool value - true : the sets have an non-void
> intersection; or - false : the sets are disjoint. So to say, it stops
> after it finds the first common element of the two sets.
> If i write it myself, even if it stops, the function still takes
> a lot of time :( ; much faster it goes with STL set-intersection but
> then of course the whole intersection set is computed.
> thanks a lot! grateful for any ideas...

This depends how the sets are implemented. STL sets are mutable balanced
binary trees, for example. In OCaml, sets are immutable so computing set
intersection is likely to be much faster (it is asymptotically faster).

In OCaml, you could write a disjoint function something like this:

let rec disjoint s1 s2 = match s1, s2 with
Empty, t2 -> true
| t1, Empty -> true
| Node(l1, v1, r1, _), t2 -> match split v1 t2 with
l2, false, r2 -> disjoint l1 l2 && disjoint r1 r2
| l2, true, r2 -> false

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

Quantcast