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

assigning the maximum of two numbers

by bageler (Hermit)
on Nov 02, 2005 at 22:45 UTC ( #505157=perlmeditation: print w/replies, xml ) Need Help??

A coworker came to me with a very simple question: How would you assign the maximum of two numbers? I.e., $a = the larger of $b and $c. Here's what I found:
Rate sort sort2 loop ternary List sort 112734/s -- -1% -39% -48% -67% sort2 113778/s 1% -- -39% -48% -67% loop 185579/s 65% 63% -- -15% -46% ternary 217375/s 93% 91% 17% -- -37% List 344926/s 206% 203% 86% 59% --
here's the benchmark script:
use List::Util qw(max); sub assignmax { @a = sort{$b<=>$a}@_; shift @a; } sub assignmax5 { @a = sort@_; pop @a; } sub assignmax2 { ($b,$c) = @_; $b > $c ? $b : $c; } sub assignmax3 { max(@_); } sub assignmax4 { my $a=undef; for (@_) { $a = $_ if $_ > $a; } $a; } @r = map {int rand 1000}(0..1); use Benchmark qw(cmpthese); cmpthese -1,{ 'sort' => sub {assignmax(@r)}, 'sort2' => sub {assignmax5(@r)}, 'ternary' => sub {assignmax2(@r)}, 'List' => sub {assignmax3(@r)}, 'loop' => sub {assignmax4(@r)}, };


So, can you think of any other ways, and are any of them faster than List::Util?

update: for those who think this is too trivial a thought, so was watching mold grow until it was turned into penicillin.

Replies are listed 'Best First'.
Re: assigning the maximum of two numbers
by sauoq (Abbot) on Nov 02, 2005 at 23:25 UTC
    So, can you think of any other ways, and are any of them faster than List::Util?

    I think this is elegant...

    sub max { $_[ $_[0] < $_[1] ] }
    I don't know how it would compare, but I'd expect favorably. I, like Aristotle, am not interested in the efficiency difference enough to benchmark.

    By the way, you can use that technique inline and avoid the function call (if you are really trying for efficiency.)

    my $max_xy = ($x,$y)[$x<$y]

    -sauoq
    "My two cents aren't worth a dime.";
    
      my $max_xy = ($x,$y)[$x<$y]

      That reminds me about a variation of this gem I seem to remember being in Effective Perl Programming. Not as efficient, but more artistic. If I remember correctly, it's like this:

      my $max_xy = [$x=>$y]->[$x<=$y];

      -xdg

      Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

        No wonder people hate perl. :-(

        I work with people who would *USE* that, too. :-(

      I just feel compelled to reply:

      my $max_xy = ($x,$y)[$x<$y]

      I have never seen that before. You get +100 Evan points for that show of cunning. I plan to write programs around this in the future. I feel it worthy to note though that you lack a special vital caveat. Your code can be borked if one utilizes $[, ex $[=1, You might want to append it slightly:

      my $max_xy = ($x,$y)[abs( ($x<$y)+$[ )];


      Evan Carroll
      www.EvanCarroll.com


      Grandfather WINS!

      Congratulations on your inabliity to pick up on a joke, your prize.. Amulet of a Sense Of Humor (+5 Sense Of Humor). With the amulet equiped your sense of humor is now: 5

      Congrats again.

        $[ is nasty, nasty, nasty, and is deprecated. If all Perl had to be written on the off chance that $[ may have changed, almost no Perl project would get completed.

        For any new code it should be completely safe to ignore $[. About the only good use I can think of for it is to write nasty obfu code, or maybe for Golf.


        Perl is Huffman encoded by design.
        I saw that used a lot over 15 years ago in BASIC code. BASIC didn't have a ternary conditional operator, but it was possible to emulate it.
        $a = $i > $j ? 6 : 10;
        could be written as the following in BASIC (knowing that false is 0 and true is -1):
        LET a = (i > j) * 4 + 10;
        just as it could be written as the following in Perl (knowing that false is 0 and true is 1):
        $a = ($i > $j) * -4 + 10;
Re: assigning the maximum of two numbers
by tilly (Archbishop) on Nov 03, 2005 at 04:37 UTC
    You may be interested to note that on the higher order Perl mailing list, Dominus and demerphq were just having a discussion about how untrustworthy Benchmark is - particularly on very fast pieces of code like the above.

    That discussion may be found here.

Re: assigning the maximum of two numbers
by duff (Parson) on Nov 02, 2005 at 22:52 UTC

    I think your benchmark is flawed. List::Util isn't as fast as you think it is. Go look at the source. And why are you looking at the speed of comparing two numbers?

    If I find some time later, I'll elucidate on why your benchmark is flawed unless I'm preempted by some monk with more free time.

    Update: Well, looks like everyone has done a good job saying the things that I first thought when I looked at your code. You're comparing apples to oranges. If you really want to benchmark "finding the max of 2 values", then you need to make sure that all of your subs do just that or if one needs to do more, then they all need to do the same extra stuff. In your subs, some copy the parameters, others don't; some use assignment, some don't; some use temp variables, some don't; etc.

    Also, while you're using the same array for all benchmarks (which is good to keep the tests "the same"), in a real life situtation which number is larger will change with time, so to get numbers that are "more realistic", rather than using a random 2 element list, you should use 2 known lists. One where the first number is larger, and one where the second number is larger. Then either average the results or report them separately (depending on what you're trying to show)

    As an aside, my initial reaction about List::Util is that "his numbers have to be wrong because I know List::Util is implemented in perl and uses the ternary op". It turns out that on the system I normally use (perl 5.8.6, List::Util 1.14) it's implemented in pure perl, but on another system I have (perl 5.8.0, List::Util 1.09_00) it's implemented in XS. In my benchmarks though, the straight ternary op is faster than List::Util::max even with the XS implementation. (I'd show my benchmarks, but having just read a thread on hop-discuss about how Benchmark.pm is broken I'm in the process of writing and using my own benchmarking routines, so take this result with a big grain of salt :-)

      I was just wondering...is curiosity not a valid reason to do things anymore? I didn't want to make any assumptions. It also lead me to thinking I might want to grab the greatest of a larger list of numbers, let's say I change my array to search to have 100 values. Taking out the ternary, which doesn't quite apply in this new context, here are the results:
      Rate sort2 sort loop List sort2 3380/s -- -9% -81% -94% sort 3725/s 10% -- -79% -93% loop 17454/s 416% 369% -- -67% List 53227/s 1475% 1329% 205% --



      Lastly, it's a meditation. Food for thought. I'm not trying to cure cancer here but you never know.

      List::Util: you forgot to read the comments. the perl stuff is only compiled if the XS fails to load.

        Oh no, I didn't mean to imply that being curious was a bad thing. It's just that this is an odd thing to be curious about the speed of execution. By all means, be extra-curious :-)

Re: assigning the maximum of two numbers
by revdiablo (Prior) on Nov 02, 2005 at 23:16 UTC

    Change the benchmark code a bit:

    And the results look quite different:

    Rate loop sort2 sort List ternary loop 105412/s -- -27% -27% -61% -72% sort2 143479/s 36% -- -1% -47% -62% sort 144807/s 37% 1% -- -46% -62% List 270490/s 157% 89% 87% -- -29% ternary 381869/s 262% 166% 164% 41% --
Re: assigning the maximum of two numbers
by GrandFather (Saint) on Nov 02, 2005 at 23:19 UTC

    Just addressing the two value case, ignoring the less interesting techniques, but considering inline and sub versions of the ternary technique I get the following:

    Prints:

    Rate List sauoqSub ternarySub sauoq te +rnary List 998323/s -- -10% -36% -75% + -86% sauoqSub 1106591/s 11% -- -29% -73% + -85% ternarySub 1550115/s 55% 40% -- -62% + -79% sauoq 4044842/s 305% 266% 161% -- + -44% ternary 7270647/s 628% 557% 369% 80% + --

    Update: added sauoq's technique


    Perl is Huffman encoded by design.
Re: assigning the maximum of two numbers
by Aristotle (Chancellor) on Nov 02, 2005 at 23:08 UTC

    The only other possibly reasonable approach I can think of is

    my $max = $candidate[0]; $max = $candidate[1] if $max < $candidate[1];

    but I don’t find the question interesting enough to actually benchmark it.

    Makeshifts last the longest.

Re: assigning the maximum of two numbers
by EvanCarroll (Chaplain) on Nov 02, 2005 at 23:08 UTC
    I too, have issues with your benchmarks. In the top you are creating a temporary array, and using shift/pop, which just isn't needed. @_, $a[0], $a-1 would suffice and be faster. Assignmax2..4 aren't recursive so they don't even remotely do the same thing Assignmax, or Assignmax5 oddly you don't push/pop/shift/unshift on the, nor do you create a temporary array. This is also probably a poor area to optimize, assuming your not mutating the entire list.

    I would imagine that List::Util would be atleast as fast as the fastest all perl solution. Logic would dictate that there is chance List::Util is optimized C (without looking at it) and in the event it isn't than someone has already done all the work your doing and figured out the fastest way to get a max().


    Evan Carroll
    www.EvanCarroll.com

      Don't underestimate all Perl solutions. See some of the later benchmarks where the use of the ternary operator has been improved!

      For an arbitary number of values the List::Util approach is very likely to be fastest, and surely the fastest to code. For the two element special case the ternary operator wins hands down.


      Perl is Huffman encoded by design.
Re: assigning the maximum of two numbers
by kirbyk (Friar) on Nov 02, 2005 at 22:56 UTC
    Edit: Sorry, I misread the question entirely.

    I would probably go with the ternary for readability in most cases, but if you're doing this in a critical part of your application, it looks like sort/shift is optimized well. Neat.
Re: assigning the maximum of two numbers
by QM (Parson) on Nov 03, 2005 at 19:06 UTC
    sub assignmax5 { @a = sort@_; pop @a; }
    I prefer this, especially for large arrays:
    sub assignmax5 { return (sort @_)[-1]; }
    It's immediately obvious, and easy to maintain.

    Update: strike

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

      But sort doesn't scale well, like List::Util 'max' does. So "especially for large arrays", you should not use sort to find the maximum.

      Caution: Contents may have been coded under pressure.

      Especially for large arrays? Wouldn't this be an O(nlogn) function? I mean, if you wanted an arbitrary number of the maximum numbers in a list, sure, you're pretty much already sorting. But for just the top 1, you should use an O(n) algorithm, which gets even more important for "large arrays".

      For short arrays, the difference between sort and looping with a ternary will be minor. For long arrays, well, it becomes a bit more important.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://505157]
Approved by kirbyk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (4)
As of 2022-10-05 14:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My preferred way to holiday/vacation is:











    Results (24 votes). Check out past polls.

    Notices?