How to find the N largest values in an array?

[dubx56]

E.g. given

my $n = 3;
my @numbers = qw( 3 5 7 2 5 9 8 7 3 6 );

I want to get 9,8,7.

[japhy]

The simplest way is just to sort the values numerically and get the top values:

my $n = 3;  # top three
my @highest = (sort { $b <=> $a } @num)[0 .. $n-1];

[Anonymous Monk]

The problem is that the values are ordered by time and i need the 3 values to be "in a row" not just the 3 highest. the purpose of this is to "read" a peak in traffic. if i just pull out 3 highest it doesnt represent an average. thanks though, im looking to see if i can somehow use this.

[merlyn]

If you mean "the three consecutive values that when summed make up the highest total", then that gives an implementation strategy:

my $where = 0;
my $sum = $num[0] + $num[1] + $num[2];
for ( 1 .. $#sum-2 ) {
  my $try = $num[$_] + $num[$_+1] + $num[$_+2];
  if ( $try > $sum ) {
    $try = $sum;
    $where = $_;
  }
}

[Anonymous Monk]

If any of the doesn't make sense, see sort, perlop, perldata, perlsyn.

use strict;

my @list_o_num = qw( 1 22 44 55 63 2 1 2 4 54 8 7 9 2 9 );
my @sorted_list_o_num = sort { $b <=> $a } @list_o_num;
my( $num_1, $num_2, $num_3 ) = @sorted_list_o_num;

This however, does not account for duplicates (9 9 7), so this approach might be better

#!/usr/bin/perl -w
use strict;
my @list_o_num = qw( 9 9 9 10 9 8 7 9 6 );
my %list_o_num = map {
  if ( exists $list_o_num{$_} ) {
    $list_o_num{$_}++;
  }
  else {
    $_ => 1;
  }
}
@list_o_num;
my @true_top_3 = sort { $b <=> $a } keys %list_o_num;

None of this is tested, but it should work (short of any typos).

Note: See blakem's comment and example here for a fix to make this solution actually work.

[blakem]

hmm... this looks really awkward:

my %list_o_num = map {
                         if(exists $list_o_num{$_})
                         {  $list_o_num{$_}++  }
                         else
                         {  $_ => 1  }
                     }
                 @list_o_num;

For one thing, you are using a hash in the same line as you declare it with my... thats bad... I think you are trying to do something like:

my %list_o_num;
$list_o_num{$_}++ for @list_o_num;

my @true_top_3 = (sort { $b <=> $a } keys %list_o_num)[0..2];

print "T3: ", join(', ',@true_top_3), "\n";

but I can't quite tell.

I would probably write that like so:

#!/usr/bin/perl -wT
use strict;

my @list_o_num = qw(9 9 9 10 9 8 7 9 6);
my %seen;
my @true_top_3 = (sort { $b <=> $a }
                       grep {!$seen{$_}++}
                            @list_o_num)[0..2];

print "T3: ", join(', ',@true_top_3), "\n";

-Blake

[fundflow]

The N largest values can be found in O(n) in the following way:

my @list_o_num = qw( 1 22 44 55 63 2 1 2 4 54 8 7 9 2 9 );

print "LIST_O_NUM: @list_o_num \n";

my @l = sort { $a <=> $b } @list_o_num[0..2];

for ( 3 .. $#list_o_num ) {
    my $n = $list_o_num[$_];

    if    ( $n > $l[2] ) { @l = ( $l[1], $l[2], $n ) }
    elsif ( $n > $l[1] ) { @l = ( $l[1], $n, $l[2] ) }
    elsif ( $n > $l[0] ) { @l = ( $n, $l[1], $l[2] ) }
}

print "l: @l \n";

* to be more precise, this is O(K*n)