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 WAA04562; Wed, 17 Apr 2002 22:05:26 +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 WAA04558 for ; Wed, 17 Apr 2002 22:05:26 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g3HK4sb27489; Wed, 17 Apr 2002 22:04:54 +0200 (MET DST) Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA04514; Wed, 17 Apr 2002 22:04:54 +0200 (MET DST) Date: Wed, 17 Apr 2002 22:04:54 +0200 From: Xavier Leroy To: Christophe TROESTLER Cc: "O'Caml Mailing List" Subject: Re: [Caml-list] The invert Benchmark Message-ID: <20020417220454.A4322@pauillac.inria.fr> References: <20020417.202615.87280210.debian00@tiscalinet.be> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: <20020417.202615.87280210.debian00@tiscalinet.be>; from debian00@tiscalinet.be on Wed, Apr 17, 2002 at 08:26:15PM +0200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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