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
[Caml-list] The invert Benchmark
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-04-17 (20:05)
From: Xavier Leroy <xavier.leroy@i...>
Subject: Re: [Caml-list] The invert Benchmark
> I found by chance the "The invert Benchmark"
> (  As you
> will notice the Caml code (even compiled) performs poorly. 

... and is poorly written.

> I guess
> part of the problem is due to using Map when Hashtbl is more suited.

Maybe not.  Actually, using Map isn't such a bad idea in this
program, because maps are already sorted.

> So I tried to rewrite the code using Hashtbl (attached to this mail).
> What I got some trouble to figure out is how to get a list of the keys
> where each of the keys appears only once.

A useful trick is to organize your hashtable differently: make it map
strings to string list ref, e.g. have only one binding for each key,
but a list of associated values.

> Another related question that popped up is: how to _efficiently_
> implement a join operation (join : string -> string list -> string is
> defined by: join c [s1;...;sn] = s1 ^ c ^ ... ^ c ^ sn) ?

Why, just look in the standard library, of course.  It's called 
String.concat, and is a lot more efficient than the atrocious
implementation found in the benchmark.

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: