Re: [Caml-list] Hashtbl or Set?

[Basile Starynkevitch <basile@starynkevitch.net>]

On Mon, 19 Sep 2011 13:09:39 -0700
Ian Zimmerman <itz@buug.org> wrote:

> 
> I need a somewhat large (thousands) set of strings, created once during
> startup and never modified after. 

You didn't tell us why you need such as set, and what kind of strings are inside. 
(I mean that if the strings are file contents -e.g. typically 100kbytes long-, it is
different than if the strings are dictionnary words or source program identifiers - e.g.
typically a dozen of bytes each-)

> What is a better choice, a (string, unit) Hashtbl.t or the Set module? 
> If the Set module still uses trees
> as it did when I was young :-), access will be logarithmic versus
> constant for Hashtbl.  But on the other hand a hash function must
> examine all of every string while the comparison of 2 strings stops at
> the first nonmatching character.

Honestly, I believe that for practical purposes, unless you have very strange
constraints, both approaches are good enough. Don't forget that too early optimization is
evil.


> I am thinking about the time to build the set as well as the probing
> time.

Make it a module, that is, your abstract data type. Then, if you discover later that this
module is a bottleneck, optimize it further.


Honestly, I think you should not care that much in the first place. (the real timing may
also depend of memory cache considerations and sizes).

Cheers.
-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***