Browse thread
Canonical Set/Map datastructure?
[
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: | 2008-03-05 (22:02) |
From: | Alain Frisch <alain@f...> |
Subject: | Re: [Caml-list] Canonical Set/Map datastructure? |
Jon Harrop wrote: > On Wednesday 05 March 2008 17:27:38 Alain Frisch wrote: >> Patricia trees work fine when the set elements can easily be represented >> as strings of bits. >> ... >> structural equality = physical equality = set equality > > This is very interesting. What are the disadvantages? I'm guessing: slow value > creation for small values and heavy memory consumption. I haven't done any serious benchmark comparing Patricia trees and OCaml's Set module. For the situations where we're using hash-consed Patricia trees, it is simply not an option to use balanced trees (that would turn almost linear algorithms into quadratic-or-more ones). Of course, hash-consing (and memoization of set operations) means extra tables and lookups, so there will be some overhead. Last time I checked, it was much more efficient to use regular hash tables rather than weak ones, but this might have changed since then. Another disadvantage is that hash-consing usually does not play well with marshaling (e.g. you need to manually traverse unmarshaled values to restore invariants). Alain