Re: [Caml-list] @, List.append, and tail recursion

[Brian Hurt <brian.hurt@qlogic.com>]

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