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: Remi VANICAT <vanicat@l...>
Subject: Re: [Caml-list] The invert Benchmark
Christophe TROESTLER <debian00@tiscalinet.be> writes:

> Dear Caml riders,
> 
> 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.  I guess
> part of the problem is due to using Map when Hashtbl is more suited.

Not exactly. Map can be very well suited if one remember that Map sort
its element. 

> 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.  I eventually went the easy
> way.  Anybody got better ideas to improve efficiency?  Could a "keys"
> function be an interesting addition to Hashtbl???
> 
> 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) ?

very poorly efficient, a far better implementation for it is :

let join c l = String.concat c l

one can, of course, use directly String.concat....

[...]

it's often better to use a hastable of list ref than what you are
doing (that is : first, check if the key is already associated with a
list ref, then if it is the case add your element to the list ref,
otherwise, add a new binding with an list ref containing only the new
element). 
-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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