From: "sasha mal" <sasha.mal@excite.com>
To: caml-list@yquem.inria.fr
Cc: jon@ffconsultancy.com
Subject: Re: [Caml-list] More efficient implementation of intersection of sets?
Date: Wed, 2 Apr 2008 09:30:25 -0400 (EDT) [thread overview]
Message-ID: <20080402133025.7ADAF8B31E@xprdmxin.myway.com> (raw)
> On Tuesday 01 April 2008 16:55:24 sasha mal wrote:
> > Dear OCaml users!
> >
> > Currently,
> >
> > Set.inter x y
> >
> > splits y into two trees, one containing elements that are bigger and the
> > other containing elements that are smaller than the top of x, then applies
> > the procedure recursively. What is the exact runtime of the algorithm?
>
> We discussed this before on this list and the result was inconclusive. Suffice
> to say, it is very fast!
If could give a pointer to the discussion, that would be great!
> > Is there a better one for the intersection for OCaml sets?
> Not likely.
I wouldn't be so sure.
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 hold 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, prcoeed analogously, i.e. search for the smallest key k>=key2 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.
The search in the trees is done by using "pointers" which are lists of trees contained in one another. E.g. [a,b,c] means that c is the root, b is one of the children of c, a is one of the children of b.
The advantage compared to the current implementation is that portions of one tree which are irrelevant for the intersection might be skipped. In the current implementation, they are rebalanced.
The used time is at most O((t1+t2)log(t1 intersection t2)) if constructors need O(1) time. A better estimation is welcome.
Could anyone compare this approach to the current implementation?
_______________________________________________
Join Excite! - http://www.excite.com
The most personalized portal on the Web!
next reply other threads:[~2008-04-02 13:30 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-04-02 13:30 sasha mal [this message]
-- strict thread matches above, loose matches on Subject: below --
2008-04-02 14:01 sasha mal
2008-04-04 17:27 ` Brian Hurt
2008-04-01 15:55 sasha mal
2008-04-01 23:42 ` [Caml-list] " Jon Harrop
2008-04-02 14:05 ` Frédéric Gava
2008-04-02 15:34 ` Mike Furr
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20080402133025.7ADAF8B31E@xprdmxin.myway.com \
--to=sasha.mal@excite.com \
--cc=caml-list@yquem.inria.fr \
--cc=jon@ffconsultancy.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).