How can I find the index of the biggest element in an array?

[Anonymous Monk]

How can I find the index of the biggest element in an array?

Originally posted as a Categorized Question.

[GrandFather]

Given an array @data containing numeric data:

my $idxMax = 0;
    
$data[$idxMax] > $data[$_] or $idxMax = $_ for 1 .. $#data;

is not only compact but, somewhat surprisingly perhaps, comparable in speed to caching $data[$idxMax] as shown in most of the other variants. A cache variant is worth using if an expensive calculation is required in the comparison or a very large array is being processed.

[tye]

my $index = 0;
my $maxval = $myarray[ $index ];
for my $i ( 0 .. $#myarray )
{
    $maxval < $myarray[$i] and
    $index = $i
        if  $maxval < $myarray[$i];
}
print "The greatest is element number $index: $myarray[$index]\n";

[satchboost]

my $index = 0;
my $maxval = $myarray[ my $index ];
for ( 0 .. $#myarray )
{
    if ( $maxval < $myarray[$_] )
    {
        $index = $_;
        $maxval = $myarray[$_];
    }
}
print "Max is index $index: $myarray[$index]\n";

[turnstep]

my $max;
my $index;
my $x = 0;
for ( @myarray )
{
    $index = $x and $max = $_
        if !defined $max or $_ > $max;
    $x++;
}
print "The winner is element number $index: $myarray[$index]\n";

[I0]

There's still a bug, if the biggest element is at index 0

[reisinge]

A one-liner where the array elements are the command line arguments:

$ perl -E 'say [ sort { $ARGV[$b] <=> $ARGV[$a] } 0..$#ARGV ]->[0]' 42
+ 1000 999 0 -1

[reisinge]

I was wondering about the efficiency of this solution so I compared it with GrandFather's solution:

# x.pl
use Benchmark qw(timethese cmpthese);

cmpthese(
    -2,
    {
        GrandFather => sub {
            my $idxMax = 0;
            $ARGV[$idxMax] > $ARGV[$_] or $idxMax = $_ for 1 .. $#ARGV
+;
            $idxMax;
        },
        reisinge => sub {
            [ sort { $ARGV[$b] <=> $ARGV[$a] } 0..$#ARGV ]->[0];
        }
    }
);

These are the results of the benchmarking:

$ perl x.pl $(seq 1 1000)
              Rate    reisinge GrandFather
reisinge    3742/s          --         -3%
GrandFather 3864/s          3%          --
$ perl x.pl $(seq 1 10000)
             Rate    reisinge GrandFather
reisinge    377/s          --         -5%
GrandFather 395/s          5%          --
$ perl x.pl $(seq 1 100000)
              Rate    reisinge GrandFather
reisinge    34.1/s          --        -18%
GrandFather 41.6/s         22%          --

GrandFathers's solution seems to be more efficient, i.e. it's faster (to run) and scales better. But mine is shorter :-).

[marioroy]

GrandFather's solution may be shorten if a short one-liner is what you're after.

# reisinge
perl -E 'say [ sort { $ARGV[$b] <=> $ARGV[$a] } 0..$#ARGV ]->[0]' 42 1
+000 999 0 -1

# GrandFather
perl -E '$m=0; $ARGV[$m] > $ARGV[$_] or $m=$_ for 1..$#ARGV; say $m' 4
[phone]

# Shorten, similar performance
perl -E '$i=0; ($ARGV[$m] > $_ or $m=$i), $i++ for @ARGV; say $m' 42 1
+000 999 0 -1

Below, please find a benchmark script for testing against a large list.

use strict;
use warnings;
use List::Util 'shuffle';
use Time::HiRes 'time';

# Return index to biggest element.

sub reisinge {
    [ sort { $_[$b] <=> $_[$a] } 0 .. $#_ ]->[0];
}

sub GrandFather {
    my $idxMax = 0;
    $_[$idxMax] > $_[$_] or $idxMax = $_ for 1 .. $#_;
    $idxMax;
}

sub biggest_elm {
    my ($idxMax,$idx) = (0,0);
    ($_[$idxMax] > $_ or $idxMax = $idx), $idx++ for @_;
    $idxMax;
}

srand 0;

my @list = shuffle 1..4e5;

for my $code (qw( reisinge GrandFather biggest_elm )) {
    no strict 'refs';
    my ($start, $idx) = (time, $code->(@list));

    printf "Index %d, Seconds (%-11s): %0.03f\n",
        $idx, $code, time - $start;
}

Regards, Mario.

Edit: Added benchmark script.

[DillonYu]

Use mod:://List::Util's reduce:

use List::Util qw /reduce/;

my @arr= qw/7 6 4 90 5 7/;

my $index = reduce {$arr[$a] > $arr[$b] ? $a : $b} (0 .. $#arr);

print "$index\n";

[salva]

and if what you need are the indexes for the $n biggest elements:

use Sort::Key::Top qw(nkeytop rnkeytop);

my @data = ( 100, -2, 5, 12, 1, 1, 6786, ...);

my @min_ix_n =  nkeytop { @data[$_] } $n => 0..$#data;
my @max_ix_n = rnkeytop { @data[$_] } $n => 0..$#data;

[jdporter]

A recursive solution.

sub _index_of_largest
{
    my $X = shift;  my $L = shift;
    my $x = $#_;    my $l = pop;
    defined $X and $L > $l and ($x,$l) = ($X,$L);
    @_ or return $x;
    unshift @_, $x, $l;
    goto &_index_of_largest
}

sub index_of_largest
{
    @_ or die;
    _index_of_largest(undef,undef,@_);
}

my $i = index_of_largest( @a );

[Skeeve]

turnstep's first answer has two bugs

1. He forgot to set $maxval after fiding a longer string
2. He forgot to consider index 0

Originally posted as a Categorized Answer.

[EdgeNosedMonkey]

I missed the square brackets in the previous reply:



%arrayHash=map {$_=> $i++} @array=(5,4,3,2,7);
print $arrayHash{pop [sort @array]};

Originally posted as a Categorized Answer.

[EdgeNosedMonkey]

Also if your question is specifically about finding the largest number, the following code should work just fine :

%arrayHash=map {$_=> $i++} @array=(-15,4,8,10,3,2,7);
print $arrayHash{pop [sort {$a<=>$b} @array]};

Originally posted as a Categorized Answer.

[Skeeve]

my $i = $#data;
my $max = $i;
$max = $data[$i] > $data[$max] ? $i : $max while $i--;
print "Max value is $data[$max], at index $max\n"

[Jenda]

I don't think it's good to scare people with a ternary operator and statement modifier in one statement. I do think

while ($i--) {
  $max = $i if $data[$i] > $data[$max];
}

would be much more readable. I'd probably write it like this though:

my $max = 0;
for (0 .. $#data) {
    $max = $_ if $data[$_] > $data[$max]
}

Update (suggested by ysth): It's actually better to start looping at index 1:

my $max = 0;
for (1 .. $#data) {
    $max = $_ if $data[$_] > $data[$max]
}

There's no point in comparing the first element to itself.

[simmisam]

my @array1 = qw(4 3 7 8 9 49 12 23 43);
 my $largest = (sort {$b <=> $a} @array1)[0];
 my ($index) = grep {$array1[$_] ~~ $largest} 0..$#array1; 
 print "Number = $largest, Index = $index\n";

[dcmertens]

I disagree. This is kinda clever, but I suspect that a single pass would be clearer. I would do this:

my @array = qw(4 3 7 8 9 49 12 23 43);
my ($largest, $largest_idx) = ($array1[0], 0);
for my $i (1 .. $#array) {
        ($largest, $largest_idx) = ($array[$i], $i)
                if $largest < $array[$i];
}
print "Largest number is $largest, at offset $largest_idx\n";

It really seems like something like this should be available in List::Util or List::MoreUtils, and I would use one of those instead of the sort+smartmatch. At any rate, I am most likely to need this sort of calculation in PDL, where I would do it like this:

use PDL;
my $data = pdl(qw(4 3 7 8 9 49 12 23 43));
my $largest_idx = $data->maximum_ind;
my $largest = $data->at($max_idx);
print "Largest number is $largest, at offset $largest_idx\n";

but PDL would be overkill for a dataset of this size.

[EdgeNosedMonkey]

You could use the Perl map function in the following way. This achieves the results in just two lines.




%arrayHash=map {$_=> $i++} @array=(5,4,3,2,7);
print $arrayHash{pop [sort @array]};

Originally posted as a Categorized Answer.