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 RAA29093; Thu, 20 Mar 2003 17:42:27 +0100 (MET) 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 RAA29121 for ; Thu, 20 Mar 2003 17:42:25 +0100 (MET) Received: from epexch01.qlogic.org ([63.170.40.3]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h2KGgOf25807 for ; Thu, 20 Mar 2003 17:42:25 +0100 (MET) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Thu, 20 Mar 2003 10:43:31 -0600 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Thu, 20 Mar 2003 10:43:31 -0600 Date: Thu, 20 Mar 2003 10:53:08 -0600 (CST) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: John Gerard Malecki cc: Caml List Subject: Re: [Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures In-Reply-To: <15993.10380.206589.498703@barrow.artisan.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 20 Mar 2003 16:43:31.0050 (UTC) FILETIME=[D6F8DCA0:01C2EEFF] X-Spam: no; 0.00; qlogic:01 caml-list:01 glue:01 pervasives:01 red-black:01 library's:01 inserting:01 ocaml:01 tree:02 gerard:02 stack:02 wrote:03 annoying:03 recursive:03 library:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, 19 Mar 2003, John Gerard Malecki wrote: > The program broke down in 2 places. First, List.concat was used to > convert the output of the fracturer from 'a list list to 'a list. Not > only is List.concat not tail-recursive but @ (Pervasives.append) is > also not tail-recursive. I modified the fracturer to directly produce > 'a list. I have a tail-recursive version of the entire list library, including append, kicking around- I'll send it to you. That fixes this problem. But thank you for proving me right- this *is* a problem :-). As for producing the tree, I'd recommend using a self-balancing tree- perhaps a Red-Black tree (which is surprisingly easy to implement in Ocaml. It's annoying that the standard library's set doesn't *quite* do what you need). Inserting an element should be O(log n), meaning you should be able to build the whole tree in O(n * log n). Hmm. Alternatively, you might also look at my Priority Search Queue implementation. This probably does more than you need, but that's better than doing less than you need :-). With PSQueue: > - fast computation of cardinality Cardinality is, or should be, O(1) (if all else, I just keep a running count of elements in the tree). > > - fast addition of single elements PSQueue is O(log n) addition. > > - fast addition of lists of elements Adding a list of k elements to a n-element PSQueue is O(k * log n). > > - fast removal of single elements in random order PSQueue is O(log n) removal of any element. Also, finding any given element given it's key is O(log n). > > - not choking on a large data size PSQueue is not tail recursive, but it only uses O(log n) stack space (it's a balanced tree). I'll send the code on and you can look at it. Brian ------------------- 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