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 WAA06316; Fri, 23 Apr 2004 22:20:11 +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 WAA06286 for ; Fri, 23 Apr 2004 22:20:10 +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 i3NKK9YM003314 for ; Fri, 23 Apr 2004 22:20:09 +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 i3NKK1IQ012403 for ; Fri, 23 Apr 2004 22:20:03 +0200 Received: from first.UUCP (uucp@localhost) by hirsch.in-berlin.de (8.12.11/8.12.11/Debian-3) with UUCP id i3NKF30r012019 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:10:06 +0200 (CEST) From: oliver@first.in-berlin.de (Oliver Bandel) Date: Fri, 23 Apr 2004 22:10:06 +0200 To: caml-list@inria.fr Subject: [oliver: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys] Message-ID: <20040423201006.GF271@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 quadratic:01 0200,:01 forwarded:97 forwarded:97 ciao:02 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:06PM -0500, John Goerzen wrote: > On Fri, Apr 23, 2004 at 02:51:41PM +0200, Xavier Leroy wrote: > > With your specification (no repetitions in the list), that function > > would run in quadratic time, which is a sure sign that lists aren't > > the right data structure here. (More generally speaking, "lists > > without repetitions" is almost always the wrong data structure.) > > But perhaps you don't really care how fast it runs, since your entire > program consumes about 1/10 of a CPU second anyway? > Depends on number of keys... n ^ 2 is less when n is low, n = 10 and n = 10000 seems not to matter much... but 10^2 and 10000^2 are a differrence that matters a lot! Ciao, Oliver ----- 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