Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Canonical Set/Map datastructure?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ 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).