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).

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

[download]
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.

Replies are listed 'Best First'.
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;
}

    [download]
    Caution: Contents may have been coded under pressure.
[reply]
[d/l]
Re: argmin & argmax
by ikegami (Patriarch) on May 13, 2025 at 00:01 UTC

    I've always wished that Sort::Key provided such functions.

    In case you're not familiar with Sort::Key, at its core is keysort KEY_GENERATOR LIST, which could be used as follows: 

    # Sort the objects according to the value of their `name` attribute.
my @sorted_objects =
   keysort { $_->name }
      @unsorted_objects;

    [download]

    It has variants. 

    # Sort the objects according to the value of their uint id
my @sorted_objects =
   ukeysort { $_->id }
      @unsorted_objects;

    [download]

    You'd think the module would also provide similar subs to find the elements that would sort first and/or last, but it doesn't.

    Your argmin and argmax sub are effectively specific variants of those missing subs.

[reply]
[d/l]
[select]
[reply]
[d/l]

        Nice ...or is it? Seeing as it returns the top x values, is the algorithm used O(n) as desired, or O(n log n) like a sort? That said, the extra log n doesn't add much, though.

[reply]
Re: argmin & argmax
by eritain (Novice) on May 11, 2025 at 04:03 UTC

    Super useful, now that I've matured in my appreciation for functional list processing thanks to map and grep and List::Util. Stolen and added to my toolkit.

    Note that my $val = $block->($_) might as well be my $val = $block->(). The value is still available to the block via $_ because for loops localize with dynamic scope.

[reply]

      There is also List::UtilsBy::max_by and List::UtilsBy::min_by which do this and have the additional feature of returning several items in list context if they all have the same value.

[reply]
[reply]
[d/l]
[select]

Back to Cool Uses for Perl