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 GAA01027; Mon, 20 Sep 2004 06:18:38 +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 GAA01589 for ; Mon, 20 Sep 2004 06:18:36 +0200 (MET DST) Received: from mproxy.gmail.com (rproxy.gmail.com [64.233.170.204]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8K4Iaj3006893 for ; Mon, 20 Sep 2004 06:18:36 +0200 Received: by mproxy.gmail.com with SMTP id 74so971580rnk for ; Sun, 19 Sep 2004 21:18:35 -0700 (PDT) Received: by 10.38.71.30 with SMTP id t30mr137476rna; Sun, 19 Sep 2004 21:18:34 -0700 (PDT) Received: by 10.38.165.38 with HTTP; Sun, 19 Sep 2004 21:18:34 -0700 (PDT) Message-ID: Date: Sun, 19 Sep 2004 23:18:34 -0500 From: Seth Fogarty Reply-To: Seth Fogarty To: skaller@users.sourceforge.net Subject: Re: [Caml-list] Re: Set and Map question Cc: caml-list@pauillac.inria.fr In-Reply-To: <1095652570.2580.298.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit References: <1095652570.2580.298.camel@pelican.wigram> X-Miltered: at nez-perce with ID 414E5A1C.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 implemented:01 2004:99 sourceforge:01 2004:99 insertions:01 precalculate:01 9660:01 glebe:01 nsw:01 sep:01 snail:02 tree:02 tree:02 checkout:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Yes, sorry, sorted. I know it is possible, I was wondering if it was implemented. On 20 Sep 2004 13:56:10 +1000, skaller wrote: > On Mon, 2004-09-20 at 13:14, Seth Fogarty wrote: > > > What I MEANT to ask is: Is there a O(n) method of set/map construction > > from a list, as opposed to the O(n log n) fold method. > > It seems to me that in general that is impossible, > since random tree insertions are at least O(log n) > in the tree size (proportional to depth). > > Perhaps you meant, assuming the list is sorted? > In that case, in theory you could precalculate > the shape of the tree just from the size, and then > fill in the elements in O(n). > > -- > John Skaller, mailto:skaller@users.sf.net > voice: 061-2-9660-0850, > snail: PO BOX 401 Glebe NSW 2037 Australia > Checkout the Felix programming language http://felix.sf.net > > -- Seth Fogarty sfogarty@gmail.com Neep-neep at large AIM: Sorrath "I know there are people in this world who do not love their fellow human beings - and I hate people like that" --Tom Lehrer. ------------------- 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