Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

argmin & argmax

by blokhead (Monsignor)
on May 03, 2005 at 21:26 UTC ( #453733=snippet: print w/ replies, xml ) Need Help??

Description: Suppose you have a list of items, and you are going to compute some expensive function on each of them. Sometimes it is convenient to have the minimum (or maximum) value of the function. Other times, it is more convenient to have the item which minimizes (or maximizes) the function (for example, what is the hash key that corresponds to the largest hash value?). And sometimes you even want both.

The latter behavior is referred to as argmin and argmax. To do this in Perl, you can always sort based on the expensive function, and then grab the min/max, but the sort is very wasteful for long lists (even with a Schwartzian Transform). Instead, here's a simple watermarking way to do it. In list context, it also returns both values of interest (the item that minimized/maximized the function, and the min/max value itself).

  • Get the largest value that an expression takes on:
    use List::Util 'max'; my $largest_val = max map { expensive_func($_) } @items;
  • Get the item which produces the largest value on an expression:
    my $largest_item = argmax { expensive_func($_) } @items;
  • Get both at once:
    my ($largest_item, $largest_val) = argmax { expensive_func($_) } @item +s;
A very simple concept, but quite useful.
sub argmax(&@) {
    my $index = undef;
    my $max   = undef;
    my $block = shift;
    for (@_) {
         my $val = $block->($_);
         if ( not defined $max or $val > $max ) {
             $max   = $val;
             $index = $_;
         }
    }
    return wantarray ? ($index, $max) : $index;
}

sub argmin(&@) {
    my $index = undef;
    my $min   = undef;
    my $block = shift;
    for (@_) {
         my $val = $block->($_);
         if ( not defined $min or $val < $min ) {
             $min   = $val;
             $index = $_;
         }
    }
    return wantarray ? ($index, $min) : $index;
}
These could also be implemented with List::Util::reduce, but just doing it by hand makes it easier to let the block to run with $_ aliased to the relevant value -- instead of fussing with $a and $b in L::U::reduce.
Comment on argmin & argmax
Download Code
Re: argmin & argmax
by Roy Johnson (Monsignor) on May 04, 2005 at 03:42 UTC
    You can tighten things up a little by initializing with the first element rather than dealing with undef:
    sub argmax(&@) { return() unless @_ > 1; my $block = shift; my $index = shift; my $max = $block->($index); for (@_) { my $val = $block->($_); ($max, $index) = ($val, $_) if $val > $max; } return wantarray ? ($index, $max) : $index; }

    Caution: Contents may have been coded under pressure.

Back to Snippets Section

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: snippet [id://453733]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (14)
As of 2014-09-30 16:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (378 votes), past polls