English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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 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