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 WAA09519; Fri, 23 Apr 2004 22:41:53 +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 WAA09504 for ; Fri, 23 Apr 2004 22:41:52 +0200 (MET DST) Received: from gatekeeper.elmer.external.excelhustler.com (gatekeeper.excelhustler.com [68.99.114.105]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3NKfpYM007356 for ; Fri, 23 Apr 2004 22:41:51 +0200 Received: from chatterbox.elmer.internal.excelhustler.com (unknown [192.168.0.12]) (using TLSv1 with cipher EDH-RSA-DES-CBC3-SHA (168/168 bits)) (Client CN "chatterbox.elmer.internal.excelhustler.com", Issuer "excelhustler.com" (not verified)) by gatekeeper.elmer.external.excelhustler.com (Postfix) with ESMTP id 4561CE013F; Fri, 23 Apr 2004 15:41:50 -0500 (CDT) Received: from localhost (localhost [127.0.0.1]) by chatterbox.elmer.internal.excelhustler.com (Postfix) with ESMTP id 01D725C007; Fri, 23 Apr 2004 15:41:50 -0500 (CDT) Received: from wile.internal.excelhustler.com (wile.internal.excelhustler.com [192.168.1.34]) by chatterbox.elmer.internal.excelhustler.com (Postfix) with ESMTP id C9E945C005; Fri, 23 Apr 2004 15:41:49 -0500 (CDT) Received: by wile.internal.excelhustler.com (Postfix, from userid 1000) id BD7854A; Fri, 23 Apr 2004 15:41:49 -0500 (CDT) Date: Fri, 23 Apr 2004 15:41:49 -0500 From: John Goerzen To: Oliver Bandel Cc: caml-list@inria.fr Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys Message-ID: <20040423204149.GA6485@excelhustler.com> References: <20040421011904.GA1411@first.in-berlin.de> <20040423145141.B3686@pauillac.inria.fr> <20040423182906.GB4117@excelhustler.com> <20040423191010.GB1506@first.in-berlin.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20040423191010.GB1506@first.in-berlin.de> User-Agent: Mutt/1.5.5.1+cvs20040105i X-Scanned-By: clamscan at chatterbox.elmer.internal.excelhustler.com 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 oliver:01 bandel:01 2004:99 quadratic:01 hashtables:01 hashtbl:01 0200,:01 0200,:01 wrote:03 wrote:03 docs:03 data:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, Apr 23, 2004 at 09:10:11PM +0200, Oliver Bandel wrote: > 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! OK, but why should we eliminate a useful function because 1% of uses of it will be slow? Make a note in the docs (like that notes that are there already that say "this function is not tail-recursive") and put it in for those that will find it useful. On another note, I really don't understand why hashtables permit duplicate keys anyway; it just doesn't seem useful to me. All my Hashtbl code uses Hashtbl.replace.... -- John ------------------- 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