Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Finding the max()/min()

by dragonchild (Archbishop)
on Nov 11, 2004 at 02:25 UTC ( #406883=perlmeditation: print w/ replies, xml ) Need Help??

In a language as cool as Perl, there are many ways of doing even the simplest task. Take finding out which of $x and $y are bigger. I can think of at least 4 ways of doing that.

How many can you think of? What about other functions that are somewhat ubiquitous in nature that you can write many ways?

Being right, does not endow the right to be rude; politeness costs nothing.
Being unknowing, is not the same as being stupid.
Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Comment on Finding the max()/min()
Select or Download Code
Re: Finding the max()/min()
by Zaxo (Archbishop) on Nov 11, 2004 at 02:38 UTC

    Here's a pair I like, similar to your delightfully symmeteric third example,

    # max my $max = ($x, $y)[$x < $y]; # min my $min = ($x, $y)[$x > $y];
    Those are slightly forthish, in lifting a logical value to arithmetic use.

    Update: As subroutines,

    sub max ($$) { $_[$_[0] < $_[1]] } sub min ($$) { $_[$_[0] > $_[1]] }
    I used prototypes there because the usual perl min and max extracts the extreme of a list, instead of from just two values.

    After Compline,
    Zaxo

Re: Finding the max()/min()
by elusion (Curate) on Nov 11, 2004 at 02:48 UTC
    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.

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

      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

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

      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.

Re: Finding the max()/min()
by pg (Canon) on Nov 11, 2004 at 03:25 UTC

    A recursive solution for a list of numbers: (the idea to get max for a list is originally gotten from elusion's post)

    use strict; use warnings; print max(1.23,2.6,55.1,1.11,4,5); print min(1.23,2.6,55.1,1.11,4,5); sub max { splice(@_, ($_[0] > $_[1]) ? 1 : 0, 1); return ($#_ == 0) ? $_[0] : max(@_); } sub min { splice(@_, ($_[0] > $_[1]) ? 0 : 1, 1); return ($#_ == 0) ? $_[0] : min(@_); }
Re: Finding the max()/min()
by monoxide (Beadle) on Nov 11, 2004 at 03:27 UTC
    A bit longer (just a little bit) but here goes. I realise that it can probably be shortened, but in the interests of brevity and my sanity here is the longer version.
    max(3,4); sub max { ($x,$y)=@_;@xd=split//,$x; if(length($x) != length($y)) { return $x if(length($x)>length($y)); return $y if(length($y)>length($x)); } @yd=split//,$y; for($i;$i<length($x);$i++) { if (ord($xd[$i])!= ord($yd[$i])) { return $y if( ord($y)>ord($x) ); return $y if(ord ($y) >ord($x )); } } } # *** UNTESTED *** # It could be used to compare binary values, # but i suppose that is outside the scope of # this post.
Re: Finding the max()/min()
by etcshadow (Priest) on Nov 11, 2004 at 04:55 UTC
    Here's an interesting one that doesn involve a comparison operator (even an obfuscated one):
    ($x + $y + abs($x - $y)) / 2
    The math behind that is: take the average of the two numbers, and then add half their difference (start half-way between, and then go up by half). So: (x+y)/2 + abs(x-y)/2, and then factor out the division by two.
    ------------ :Wq Not an editor command: Wq

      Very cool. <nitpick>...but there's still a comparison; it's just hidden in the abs() function: (roughly:) abs(x) := x >= 0 ? x : -x.</nitpick>

      [OT] Reminds me of a programming assignment where we were supposed to put the square roots of the integers from 1-100 inclusive into two groups with roughly equal sums. I used the fact that sqrt(x) + sqrt(x+3) is very close to sqrt(x+1) + sqrt(x+2) and managed to outperform all the other submissions by several orders of magnitude in both speed and "difference in sum". (Yea math!)

        The nitpick is perfectly valid... I almost made a note of it. Of course, it would be possible (though silly) to implement an abs function without a comparison, such as sub abs { sqrt($_[0]**2) }.

        There's probably some mathematical identity for the abs of the difference of two numbers... but I didn't get enough sleep last night to think about what it might be :-)

        ------------ :Wq Not an editor command: Wq
Re: Finding the max()/min()
by tmoertel (Chaplain) on Nov 11, 2004 at 05:12 UTC
    As others have mentioned, it's handy to capture min and max logic in subroutines for reuse. Most times, if you have a max subroutine, for example, it will take an array and return the maximum element. That's great if you want to hold all of your values in memory, but what if you don't? What if you want to compute your maximum iteratively, e.g., one number at a time while reading from a file?

    As I offered in Re: getting the highest value in a simpler way, we can encapsulate our logic inside of a closure-based factory function that makes "maximum finders":

    sub make_max_finder { my $max; sub { for (@_) { $max = $_ if !defined $max || $_ > $max } $max; } }
    The nice thing about this approach is that the logic is captured in one place and yet we can use it both on big arrays and upon iterated-over data. The array method:
    make_max_finder->(1..10); # 10
    The iterative, light-on-memory method:
    my $max_finder = make_max_finder(); $max_finder->($_) while <>; $max_finder->(); # retrieve maximum

    Cheers,
    Tom

Re: Finding the max()/min()
by brian_d_foy (Abbot) on Nov 11, 2004 at 06:01 UTC
    Nobody likes the max() function from List::Util, I guess.
    --
    brian d foy <bdfoy@cpan.org>
      Is List::Util now part of the core? It wasn't in 5.6, which made me not use it.

      Being right, does not endow the right to be rude; politeness costs nothing.
      Being unknowing, is not the same as being stupid.
      Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
      Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

        It is now; that's why I use it. I would be reluctant to use a non-core module for such trivial functions.

        Whether or not you can get away with expecting that your users will have either perl-5.8+ or install List::Util on an older version depends on your particular circumstances.

Re: Finding the max()/min()
by Zed_Lopez (Chaplain) on Nov 11, 2004 at 17:49 UTC

    There's also the Quantum::Superpositions approach:

    sub min { eigenstates( any(@_) <= all(@_) ) } sub max { eigenstates( any(@_) >= all(@_) ) }

    In the real world, I'd use List::Util::max; if I wrote my own, it'd be this small variation on solutions above:

    sub max { my $max = shift; $max = $max > $_ ? $max : $_ for @_; return $max }
Re: Finding the max()/min()
by cLive ;-) (Parson) on Nov 11, 2004 at 18:09 UTC
    $max = $x%$y-$x ? $x : $y
    cLive ;-)

    update: d'oh. caveat - "for $x and $y both +ve integers lol...

      $x=1; $y=0; $x=-1; $y=2; $x=1.2; $y=2;


      -- All code is 100% tested and functional unless otherwise noted.
        Ahh, good point ;-)

        Serves me right for trying to be creative on a Windows box sans Perl :)

        cLive ;-)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://406883]
Approved by neilh
Front-paged by neilh
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (11)
As of 2014-08-20 15:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (118 votes), past polls