Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Reading a large text file
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-05-01 (15:43)
From: Rahul Siddharthan <rsidd@o...>
Subject: Re: [Caml-list] Reading a large text file
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.


To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: