Re: [Caml-list] More efficient implementation of intersection of sets?

["sasha mal" <sasha.mal@excite.com>]

> I'm thinking of an alternative approach which inserts keys one at a time.

> Basically, we go through both trees simultaneously, starting with smallest

> nodes of both trees. If two nodes with the same key are seen, the are inserted

> into a new tree that will contain the intersection; then the pair of nodes with

> next larger keys is taken. Otherwise, if, say, key1<key2, then we search for

> the smallest key k>=key2 inside the first tree. If k=key2, we add k into the

> new tree and proceed to the next pair. If k>key2, we proceed with the pair 

> (k, key2) instead of (key1, key2). For key1>key2, proceed analogously, i.e.

> search for the smallest key k>=key1 in the second tree. If at some point of

> time no "larger" key is found in one of the two original trees, the new tree

> where we insert elements to contains exactly the intersection.



[Small corrections.]



By the way, the current implemented procedure always splits the second tree, regardless of the sizes of the trees. Imagine that we have two trees of very different sizes (e.g. with 5 and 10^5 elements). What tree should be split then?

_______________________________________________
Join Excite! - http://www.excite.com
The most personalized portal on the Web!