Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
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 perusing the Monastery: (8)
As of 2015-07-05 21:33 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 (68 votes), past polls