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