Version française
Home     About     Download     Resources     Contact us    
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: -- (:)
From: Jean-Christophe Filliâtre <Jean-Christophe.Filliatre@l...>
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.

Regarding memory consumpion, it is true that hash-consing tables are
using memory, but sharing structurally equal values may also save some
space; see for instance the benchmarks on page 4 of
http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.ps

-- 
Jean-Christophe