Browse thread
[Caml-list] intersecting huge integer sets
[
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: | 2002-08-28 (12:29) |
From: | Tibor Simko <tibor.simko@c...> |
Subject: | Re: [Caml-list] intersecting huge integer sets |
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