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
Estimating the size of the ocaml community
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-06 (14:59)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] The boon of static type checking
On Sun, 2005-02-06 at 23:16, Gerd Stolpmann wrote:

> For your problem, I would guess that a hash table (in phase 1) plus
> sorting (in phase 2) is the relatively best solution (from your
> description). That avoids a lot of overhead compared to Map, especially
> memory management consumes much less time.

If you know something of the distribution of your keys,
which are strings, you can also make this much faster
by indexing using some suitable monotonic function
on the string prefix, and only sorting equivalent

EG, 64K word array of lists, indexed by first two
bytes of the string, then 64K sorts.

If your keys are not well distributed on the first
two bytes, use a monotonic hashing function.

John Skaller,
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language