Re: [Caml-list] intersecting huge integer sets

[Tibor Simko <tibor.simko@cern.ch>]

Hello

Thanks for all the suggestions.  Here's a little summary [figures
below obtained by studying some special cases]:

As for Ptset, I found that Patricia trees are good in sparse
situations only: here they may be about 2x faster than Hashtbl.
However, the situation to optimize is rather the dense set
intersection performance, as said in my previous example.  Here Ptset
often performs 3x slower than Hashtbl: even the ordinary Set module
intersection is often faster than Ptset's one.  Overall, having tried
several sparse-dense situations, I found that Hashtbl sets perform
much better than Ptset sets.

As for Bitv, the set operations are indeed very fast for dense sets,
often an order of magnitude faster than Hashtbl.  For sparse sets,
Hashtbl may be faster but Bitv performance is acceptable here.  And,
since marshaling of Bitv vectors is blazingly fast too (often two
order of magnitudes faster than Hashtbl), it looks like Bitv is the
ideal overall data structure for my problem. :-)

Tibor
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners