From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA04794; Wed, 17 Apr 2002 22:14:07 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA04790 for ; Wed, 17 Apr 2002 22:14:06 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from mel-rto6.wanadoo.fr (smtp-out-6.wanadoo.fr [193.252.19.25]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g3HKE5b27738 for ; Wed, 17 Apr 2002 22:14:05 +0200 (MET DST) Received: from mel-rta2.wanadoo.fr (193.252.19.152) by mel-rto6.wanadoo.fr; 17 Apr 2002 22:14:05 +0200 Received: from debian (80.8.81.178) by mel-rta2.wanadoo.fr; 17 Apr 2002 22:13:54 +0200 Received: from moi by debian with local (Exim 3.35 #1 (Debian)) id 16xvoS-0001Fh-00 for ; Wed, 17 Apr 2002 22:13:56 +0200 To: caml-list@inria.fr Subject: Re: [Caml-list] The invert Benchmark References: <20020417.202615.87280210.debian00@tiscalinet.be> From: Remi VANICAT Date: 17 Apr 2002 22:13:56 +0200 In-Reply-To: <20020417.202615.87280210.debian00@tiscalinet.be> Message-ID: <87k7r6jd6j.dlv@wanadoo.fr> User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-15 Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Christophe TROESTLER 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