More efficient implementation of intersection of sets?

More efficient implementation of intersection of sets?

[sasha mal]

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? Is there a better one for the intersection for OCaml sets?



Regards

Sasha





 --- On Fri 03/14, Alain Frisch < alain@frisch.fr > wrote:

From: Alain Frisch [mailto: alain@frisch.fr]

To: sasha.mal@excite.com

     Cc: caml-list@yquem.inria.fr

Date: Fri, 14 Mar 2008 08:38:41 +0100

Subject: Re: [Caml-list] BDDs in ocaml



sasha mal wrote:> I wonder whether anyone has a BDD (binary decision diagram)> implementation in ocaml. Ocaml interfaces to external BDD> implementations in other languages (like Cudd) are of no use to me.I've seen many implementation of BDDs in OCaml, but none of them implements automatic reordering of variables (which is by far the most complex part of serious BDD packages). For some applications, this is really a must. Why is it impossible for you to use to an external BDD implementation?-- Alain

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

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

[Jon Harrop]

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!

> Is there a better one for the intersection for OCaml sets?

Not likely. OCaml's implementation is already vastly more efficient than any 
other language I have ever seen (e.g. C++). Your next best bet is probably to 
parallelize the algorithm to improve the performance but that is extremely 
difficult to do without a concurrent GC. Frederic Gava did some work on this 
in OCaml. I am working on the same problem in F#.

Failing that, you might want to apply some of the stock optimizations to the 
Set module, such as a Node1 type constructor for nodes with a value but no 
child nodes. That can improve performance by 30%.

Alternatively, you may prefer to ditch immutable structures and opt for a 
hashset, which can be many times faster but is much more difficult to use 
because it is mutable.

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

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

[Frédéric Gava]

Dear John, Sasha and Caml-list

> Not likely. OCaml's implementation is already vastly more efficient than any 
> other language I have ever seen (e.g. C++). Your next best bet is probably to 
> parallelize the algorithm to improve the performance but that is extremely 
> difficult to do without a concurrent GC. Frederic Gava did some work on this 
> in OCaml. I am working on the same problem in F#.

You can have parallel sets without a concurrent GC : each processor has 
a subset of your initial set and you can distribute the elements using a 
hash function from element to the number of processor "p" (there is so 
"p" ocaml programs that runs and thus "p" GC). A random function can be 
used in general and generate a quick good load balancing.

You can have more information here :
http://lacl.univ-paris12.fr//gava/papers/gava_ppl_2008.pdf

Note, that I used our "under development library" but this work can be 
done using OCaml-MPI


Frédéric G.

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

[Mike Furr]

sasha mal wrote:
> 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? Is there a better one for the intersection for OCaml
> sets?

The general algorithm is linear in the size of both sets in the worst 
case, however it can be quite a bit faster in many circumstances.  See 
the paper "Implementing Sets Efficiently in a Functional Language" by 
Stephen Adams[1] for a more detailed discussion.  I haven't looked at 
INRIA's exact implementation very closely, so they may do some extra 
tricks not discussed there, but it certainly appears to use this general 
technique.

-Mike

[1] - http://citeseer.ist.psu.edu/162336.html