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 WAA06373; Fri, 23 Apr 2004 22:20:23 +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 WAA06363 for ; Fri, 23 Apr 2004 22:20:22 +0200 (MET DST) Received: from hirsch.in-berlin.de (hirsch.in-berlin.de [192.109.42.6]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3NKKLYM003347 for ; Fri, 23 Apr 2004 22:20:21 +0200 X-Envelope-From: oliver@first.in-berlin.de X-Envelope-To: Received: from hirsch.in-berlin.de (localhost [127.0.0.1]) by hirsch.in-berlin.de (8.12.11/8.12.11/Debian-3) with ESMTP id i3NKK1Ic012403 for ; Fri, 23 Apr 2004 22:20:20 +0200 Received: from first.UUCP (uucp@localhost) by hirsch.in-berlin.de (8.12.11/8.12.11/Debian-3) with UUCP id i3NKF3Kb012014 for inria.fr!caml-list; Fri, 23 Apr 2004 22:15:03 +0200 Received: by first.in-berlin.de via sendmail from stdin id (Debian Smail3.2.0.114) Fri, 23 Apr 2004 22:09:57 +0200 (CEST) From: oliver@first.in-berlin.de (Oliver Bandel) Date: Fri, 23 Apr 2004 22:09:57 +0200 To: caml-list@inria.fr Subject: [oliver: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys] Message-ID: <20040423200957.GE271@first.in-berlin.de> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline User-Agent: Mutt/1.3.28i X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; oliver:01 in-berlin:01 oliver:01 bandel:01 caml-list:01 hashtbl:01 caml-list:01 hashtbl:01 2004:99 2004:99 avoids:01 hash:01 retrieve:99 implemented:01 bindings:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk ----- Forwarded message from oliver ----- To: John Goerzen Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys On Fri, Apr 23, 2004 at 01:29:35PM -0500, John Goerzen wrote: > On Fri, Apr 23, 2004 at 06:04:07PM +0200, Xavier Leroy wrote: > > > Perhaps I'm all wrong, but when I have to get rid of repetitions in a > > > list, I first sort it in O(n log n), then remove the repetitions in O(n). > > > Jean-Baptiste. > > > > OK, fair enough :-) The point I was trying to make (not very well, I > > agree) is that "list without repetition" or "sorted list without > > repetition" is often not the best data structure for the job. > > And a keys function need not necessarily avoid repetition anyway. > [...] It ONLY makes sense to have a keys function that avoids repitition! Anything else can be done with List.iter and List.fold from the outside of the Hashtbl-module implementation! But explicitly ONLY a keys-function that reports keys only ONCE is a valid candidate for going into the standard lib! Ciao, Oliver P.S.: If you want to have the keys reported as often as there are bindings to them, you can use List.length (Hashtbl.find_all ht key) to get the number of bindings for the key. ( And then you can print several times that key_n is used inside the hash. IMHO this is called redundance. :) ) This is above not much code and does not looks like a performance problem, when doing outside the Hash-implementation. But to retrieve a non-repitional keys-list, it is much more work to do and it also seems to be much more efficient implemented when done inside the Hashtbl-lib's code. What keys to use in the above code-snippet? Well, you could do it like this: Get the keys with Hashtbl.keys and for each of the keys use the above code snippet to get the number of entries and report this ONCE. :) (or many times, if you really want to ;-)) ----- End forwarded message ----- ------------------- 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