Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re^3: Finding the max()/min()

by elusion (Curate)
on Dec 18, 2004 at 17:26 UTC ( #415876=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Finding the max()/min()
in thread Finding the max()/min()

It's normally best to end recursive solutions with the recursive call. That allows the compiler to use tail-recursion to speed up the solution.

Of course, in Perl you need to jump through a few hoops to do use tail-recursion, so I mentioned but didn't include it in my original node. But with a bit if tinkering you can use it, and here it is now:

sub max { my $max = shift; my $next = shift; return $max if not $next; unshift @_, $max > $next ? $max : $next; goto &max; }
Which I estimate to be about 10x faster on a random 5000 element list. (Exact benchmarks are left to the reader as an exercise :-).

I wonder if Ponie (Perl 5 On New Internals Engine) will be able to detect and use tail-recursion.


Comment on Re^3: Finding the max()/min()
Download Code
Re^4: Finding the max()/min()
by sleepingsquirrel (Hermit) on Dec 19, 2004 at 01:40 UTC
    There's a bug in that code, try finding the max of this list...
    @a = (1,0,3,2);


    -- All code is 100% tested and functional unless otherwise noted.
      Good catch; I forgot the edge case. Here's the fix:
      sub max { my $max = shift; return $max if not @_; my $next = shift; unshift @_, $max > $next ? $max : $next; goto &max; }
Re^4: Finding the max()/min()
by Aristotle (Chancellor) on Dec 19, 2004 at 05:45 UTC

    That's all well and nice, but my goal was to use an approach which directly generalizes from the specific case of a two element list. As you'll also notice I used the value returned from the recursive call twice, it's both kind of difficult and beside the point to work on tail recursion here. Noone in their right mind writes a recursive max() outside a functional language anyway, and in a pure functional language I'd just write max( @l ) twice and let the compiler/VM figure out that the result need only be calculated once.

    In any case, your new approach is just a variation on what was already posted in the parent node — no need for repetition…

    Makeshifts last the longest.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://415876]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (13)
As of 2014-10-23 20:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (129 votes), past polls