English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
More efficient implementation of intersection of sets?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-04-02 (14:05)
From: Frédéric_Gava <gava@u...>
Subject: Re: [Caml-list] More efficient implementation of intersection of sets?
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 :

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

Frédéric G.