Version française
Home     About     Download     Resources     Contact us    
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: -- (:)
From: Xavier Leroy <xavier.leroy@i...>
Subject: Re: [Caml-list] The invert Benchmark
> I found by chance the "The invert Benchmark"
> (http://www.lib.uchicago.edu/keith/crisis/benchmarks/invert/).  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 caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners