Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
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 taking refuge in the Monastery: (18)
As of 2015-07-01 20:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (19 votes), past polls