Browse thread
Re: [Caml-list] More efficient implementation of intersection of sets?
- sasha mal
[
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: | 2008-04-02 (14:01) |
From: | sasha mal <sasha.mal@e...> |
Subject: | Re: [Caml-list] More efficient implementation of intersection of sets? |
> 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!