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 WAA03747; Thu, 30 Jan 2003 22:48:04 +0100 (MET) 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 WAA03443 for ; Thu, 30 Jan 2003 22:48:03 +0100 (MET) Received: from epexch01.qlogic.org ([63.170.40.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h0ULm1v00743 for ; Thu, 30 Jan 2003 22:48:02 +0100 (MET) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Thu, 30 Jan 2003 15:47:40 -0600 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Thu, 30 Jan 2003 15:47:40 -0600 Date: Thu, 30 Jan 2003 15:57:14 -0600 (CST) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: Olivier Andrieu cc: Ocaml Mailing List Subject: Re: [Caml-list] @, List.append, and tail recursion In-Reply-To: <15929.37032.3235.338843@karryall.dnsalias.org> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 30 Jan 2003 21:47:40.0241 (UTC) FILETIME=[3618AC10:01C2C8A9] Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, 30 Jan 2003, Olivier Andrieu wrote: > > list1: 1.462s > > list2: 1.757s > > list3: 1.824s > > There's an assert in setcdr : it's important because the first > argument mustn't be an empty list. It's never the case here, so you > can safely compile with -noassert. Doh! OK- now, compiling with -noassert drops the time to 1.457 seconds (same machine, same environment)- to slightly better than the recursive version. And for the record, I just tested with appending to a list of 500,000 elements, and it worked OK. > > On my hardware list3 seems to be a teeny bit faster than list1 but > anyway, since list2 is just barely slower, I'm not sure it's worth the > trouble. > Correctness rates higher in my book than performance. I think it's bad that @/List.append die due to stack overflow if the lists are too long. I'd perfer the reversing solution- which works correctly so long as there is enough memory- over the recursive solution for that reason alone. Your code is even better. It gives the performance of the recursive version and the correctness of the reversing code- better yet, it doesn't allocate two whole copies of the array, allowing the code to work correctly in even more cases (when there is enough memory for one copy of the list but not two). 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