argmin & argmax

[blokhead]

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.

[Roy Johnson]

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