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 UAA30803; Fri, 23 Apr 2004 20:25:46 +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 UAA31092 for ; Fri, 23 Apr 2004 20:25:35 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3NIPYYM019129 for ; Fri, 23 Apr 2004 20:25:34 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1BH5Mj-000CAH-Hn for caml-list@inria.fr; Fri, 23 Apr 2004 18:25:33 +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 19:21:45 +0100 User-Agent: KMail/1.5.4 References: <20040421011904.GA1411@first.in-berlin.de> <40891494.5030508@ens-lyon.org> <20040423180407.A20341@pauillac.inria.fr> In-Reply-To: <20040423180407.A20341@pauillac.inria.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200404231921.45227.jdh30@cam.ac.uk> 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; caml-list:01 hashtbl:01 2004:99 quadratic:01 hashtbl:01 helper:01 helper:01 rec:01 match:02 wrote:03 iter:03 let:04 let:04 cheers:06 fold:07 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Friday 23 April 2004 2:05 pm, Jean-Baptiste Rouquier wrote: > >With your specification (no repetitions in the list), that function > >would run in quadratic time, > > 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. I have no idea what I'm talking about, but does this function not do what you want in O(n): let hashtbl_keys tbl = let rec helper k d l = match l with [] -> [k] | ok::t -> if k=ok then l else k::l in Hashtbl.fold helper tbl [] because Hashtbl's iter and fold present duplicate keys subsequently? 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