Re: [Caml-list] looping recursion

[Daniel Andor <da209@cam.ac.uk>]

On Wednesday 28 July 2004 10:22 pm, brogoff wrote:
> On Wed, 28 Jul 2004, Jon Harrop wrote:
> > On Wednesday 28 July 2004 17:38, brogoff wrote:
> > > > brogoff wrote:
> > > > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000
> > > > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow
> > > > > stack.
[...]
> > What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing
> > the size of the VM's stack, using native code or even writing your own,
> > tail-recursive map?
>
> I'm pretty damned well aware that I can reverse a rev mapped list. 

If you've got the mutable list version of map to hand, and you are happy with 
that, then that's clearly the way to go.

But the rev version of map is the same linear complexity as all the map 
functions, and is not much more inefficient than the stack version: CPU or 
memory-wise (given my limited understanding of the GC).  So if you were happy 
with List.map, except that it blew up on you, then you should definitely be 
happy with List.rev (List.rev_map ..).

Lemme try it out (10^6 elements):

ocamlc:
rev rev_map version:
 2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
vanilla map:
 7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)

ocamlopt:
rev rev_map version:
 1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
vanilla map:
 2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)

Wow, that was unexpected! 

> Does it occur to you that that is not efficient? 

Not any more!

Daniel.

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