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 XAA13893; Fri, 23 Apr 2004 23:35:27 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA13914 for ; Fri, 23 Apr 2004 23:35:26 +0200 (MET DST) Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i3NLZPjq030018 for ; Fri, 23 Apr 2004 23:35:26 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay03.plus.net with esmtp (Exim) id 1BH8KT-000Oz2-Ir for caml-list@inria.fr; Fri, 23 Apr 2004 21:35:25 +0000 From: Jon Harrop Organization: University of Cambridge To: caml-list@inria.fr Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys Date: Fri, 23 Apr 2004 22:31:36 +0100 User-Agent: KMail/1.5.4 References: <20040421011904.GA1411@first.in-berlin.de> <20040423180407.A20341@pauillac.inria.fr> <200404231921.45227.jdh30@cam.ac.uk> In-Reply-To: <200404231921.45227.jdh30@cam.ac.uk> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200404232231.36872.jdh30@cam.ac.uk> X-Miltered: at nez-perce by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 hashtbl:01 realised:01 defintions:01 hashtbl:01 bin:01 external:03 somewhere:04 suspect:05 meant:05 output:05 cheers:06 guess:06 keys:08 keys:08 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk I just realised that we may all be using different defintions for the notion of time-complexity. My function performed "n" operations where "n" is the number of keys including duplicates. It may be possible to write a routine (which would need to be in Hashtbl, I think) which could do this in "n" operations where "n" is the number of unique keys (i.e. the size of the output list). I guess that was what the original poster meant. I suspect Hashtbl allows different keys in the same bin, so the actual number of operations will be somewhere between the two but could be made considerably faster than my external function. I should also say that I have never had any need for this function. What do you guys use it for? Cheers, Jon. ------------------- 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