Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

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

by Aristotle (Chancellor)
on Dec 18, 2004 at 02:15 UTC ( #415817=note: print w/ replies, xml ) Need Help??


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

Here's another recursive form:

sub max { my( $i, @l ) = @_; my $j = @l ? max( @l ) : $i; return $i > $j ? $i : $j; }

And for that matter, an iterative form:

sub max { $_[ 0 ] < $_[ -1 ] ? shift : pop while @_ > 1; return @_; }

Makeshifts last the longest.


Comment on Re^2: Finding the max()/min()
Select or Download Code
Replies are listed 'Best First'.
Re^3: Finding the max()/min()
by elusion (Curate) on Dec 18, 2004 at 17:26 UTC
    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.

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

      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://415817]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (7)
As of 2015-07-08 06:27 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 (94 votes), past polls