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 TAA26595; Fri, 23 Apr 2004 19:24:27 +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 TAA26579 for ; Fri, 23 Apr 2004 19:24:26 +0200 (MET DST) Received: from mail-in-01.arcor-online.net (mail-in-01.arcor-online.net [151.189.21.41]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3NHOPYM010259 for ; Fri, 23 Apr 2004 19:24:25 +0200 Received: from diebuntekuh.de (dialin-212-144-208-103.arcor-ip.net [212.144.208.103]) by mail-in-01.arcor-online.net (Postfix) with ESMTP id AD3CBBD09CE for ; Fri, 23 Apr 2004 19:24:24 +0200 (CEST) Received: by diebuntekuh.de (Postfix, from userid 500) id C2244608EC0; Fri, 23 Apr 2004 19:27:23 +0200 (CEST) To: OCaml List Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys References: From: Christoph Bauer Date: Fri, 23 Apr 2004 19:27:23 +0200 In-Reply-To: (Brian Hurt's message of "Fri, 23 Apr 2004 11:06:06 -0500 (CDT)") Message-ID: User-Agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii 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 bauer:01 bauer:01 accum:01 accum:01 hashtbl:01 3..:99 expr:01 .25:99 shifted:01 rec:01 writes:01 algorithm:03 let:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Brian Hurt writes: > let uniq lst = > let rec loop accum = function > | [] -> List.rev accum > | x :: [] -> List.rev (x :: accum) > | x :: y :: t -> > if (x = y) then > loop accum (x :: t) > else > loop (x :: accum) (y :: t) > in > loop [] lst > ;; I found these lines in my code: let unique list = let h = Hashtbl.create (2*List.length list) in List.filter (fun a -> let known = Hashtbl.mem h a in Hashtbl.add h a true; not known) list On average Hashtbl.mem should take 2 accesses. So this algorithm runs in O(n). (But the worst case is very bad.) Regards, Christoph Bauer -- beginfig(1)u=3cm;draw fullcircle scaled 2u;x0=x1=y1=x2=y3=0;-y0=y2=x3=1u; filldraw z0..{left}z1{left}..z2{curl 1}..z3..z0..cycle;def t(expr p)=fullcircle scaled .25u shifted(0,p*u);enddef;unfill t(.5);fill t(-.5);endfig;bye ------------------- 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