Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: Finding the max()/min()

by elusion (Curate)
on Nov 11, 2004 at 02:48 UTC ( #406887=note: print w/ replies, xml ) Need Help??


in reply to Finding the max()/min()

What I really like is writing generic min/max routines that handle more than two variables. They show the beauty of recursive functions, even though Perl doesn't handle tail-recursion1.

Iterative:

sub max { my ($max, @vars) = @_; for (@vars) { $max = $_ if $_ > $max; } return $max; }
Recursive:
sub max { my ($max, $next, @vars) = @_; return $max if not $next; return max( $max > $next ? $max : $next, @vars ); }
Interestingly enough, though this example works well in several languages, Perl's iterative version is remarkably short; I've never noticed this before. I guess I just proved myself wrong. 1Okay, so this isn't strictly true. Using a magic goto with the & sigil and @_, you can fake it. But it's not very pretty.

Update: Fixed my mistake. Thanks, pg. (I always want to use postmodifier if and for in the same statement.) Update: Okay, so I should test my code before I post. Or find where I left my brain. Snippet 2 is fixed.


Comment on Re: Finding the max()/min()
Select or Download Code
Re^2: Finding the max()/min()
by pg (Canon) on Nov 11, 2004 at 02:52 UTC

    Update:

    Per elusion's update, he has already fixed both solutions.

    ============

    Your solution one does not compile.

    Your solution two does not work, and it does not print anything:

    use strict; use warnings; print max(1.23,2.6,55.1,4,5); sub max { my ($max, $next, @vars) = @_; return if not $next; return max( $max > $next ? $max : $next, @vars ); }
Re^2: Finding the max()/min()
by itub (Priest) on Nov 11, 2004 at 04:32 UTC
    Perhaps this will count as "cheating" for the purpose of this thread, but I just do this to find the min/max of a list

    use List::Util qw(min max); $min = min @list; $max = max @list;
    ;-)

      A moderate annoyance of List::Util::m(in|ax) is that they dont operate on tied values or situations where there is some form of indirection involved (like finding the key whose value in a hash is the lowest). Then List::Util::reduce() is your friend:

      $min = reduce { ($a,$b)[$a < $b] } @list; $min_key = reduce { ($a,$b)[$x{$a} < $x{$b}] } keys %x;

      Working out max is left as an exercise :-)

      ---
      demerphq

Re^2: Finding the max()/min() (stmt modifier form)
by demerphq (Chancellor) on Nov 11, 2004 at 10:47 UTC
    sub max { my $max=shift; $max < $_ and $max = $_ for @vars; return $max; }

    Is marginally shorted and probably faster, but commits what some would call the crime of logic based control flow.

    ---
    demerphq

Re^2: Finding the max()/min()
by sleepingsquirrel (Hermit) on Nov 11, 2004 at 19:47 UTC
    Your recursive version of max is broken for lists like (-1,0,1,2) and (-1,undef,1,2). i.e. the code assumes it is at the end of the list whenever $next==0 or $next==undef (which isn't true in general). Here's a snazzy (if not the most efficient) recursive version with a hat tip to Zaxo...
    sub max { my ($x, @xs) = @_; @xs ? ($x, max(@xs))[$x < max(@xs)] : $x }


    -- All code is 100% tested and functional unless otherwise noted.
      Your solution is calling max(@xs) twice each step. This leads to O(2^n) growth for what should be an O(n) problem. Modifying it slightly to call max once and save the value in a temp variable should save considerable time on long lists.
      sub max { my ($x, @xs) = @_; @xs ? do { my $m = maxdo(@xs); ($x, $m)[$x < $m] } : $x; }
Re^2: Finding the max()/min()
by Aristotle (Chancellor) on Dec 18, 2004 at 02:15 UTC

    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.

      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.

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (4)
As of 2014-11-29 03:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (203 votes), past polls