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 RAA31311; Sat, 1 May 2004 17:43:56 +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 RAA31307 for ; Sat, 1 May 2004 17:43:55 +0200 (MET DST) Received: from scaup.mail.pas.earthlink.net (scaup.mail.pas.earthlink.net [207.217.120.49]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i41FhsEV020787 for ; Sat, 1 May 2004 17:43:54 +0200 Received: from user-0cdfepc.cable.mindspring.com ([24.215.187.44] helo=bluerondo) by scaup.mail.pas.earthlink.net with smtp (Exim 3.33 #1) id 1BJwef-0004B6-00 for caml-list@inria.fr; Sat, 01 May 2004 08:43:53 -0700 Received: (qmail 5340 invoked by uid 1002); 1 May 2004 15:43:51 -0000 Date: Sat, 1 May 2004 11:43:51 -0400 From: Rahul Siddharthan To: Brian Hurt Cc: Andr? Luiz Moura , caml-list@inria.fr Subject: Re: [Caml-list] Reading a large text file Message-ID: <20040501154351.GA5218@online.fr> References: <20040428152813.47355.qmail@web60608.mail.yahoo.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Operating-System: DragonFly 1.0-CURRENT i386 User-Agent: Mutt/1.5.6i X-Miltered: at nez-perce with ID 4093C5BA.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 appending:01 arrays:01 ocaml:01 begining:02 seems:05 brian:06 traverse:07 i'm:07 i'm:07 lists:91 guessing:09 puzzled:10 solution:10 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Brian Hurt said on May 1, 2004 at 09:03:56: > But what I'm guessing is happening is that you are appending (adding to > the end of) your list, and that this is what is killing you. To add an > element to the *end* of a list, Ocaml has to completely reallocate the > entire list- turning what you might think is an O(1) operation into an > O(n) operation. I'm pretty puzzled by that: why would it have to do that? Arrays, yes, but lists, can't it just traverse the existing list to its end and then add a new element? It's still O(n) but no reallocation. > The solution to this is to build the list backwards- instead of adding > things to the end of the list, add them to the begining. Then, when > you're done, just reverse the list using List.rev. Yes that seems best. Rahul ------------------- 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