### How to find the N largest values in an array?

by Zombie dubx56 (Initiate)
 on Oct 03, 2001 at 22:57 UTC Need Help??
Zombie dubx56 has asked for the wisdom of the Perl Monks concerning the following question:

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.

Replies are listed 'Best First'.
Re: How to find the N largest values in an array?
by japhy (Canon) on Oct 03, 2001 at 23:04 UTC
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];
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.
Re: How to find the N largest values in an array?
by merlyn (Sage) on Oct 04, 2001 at 00:16 UTC
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 = \$_;
}
}
Re: How to find the N largest values in an array?
by Anonymous Monk on Oct 04, 2001 at 04:51 UTC
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.

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

Re: How to find the N largest values in an array?
by fundflow (Chaplain) on Oct 04, 2001 at 14:45 UTC
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)

Create A New User
Node Status?
node history
Node Type: perlquestion [id://116538]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2018-03-23 00:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (286 votes). Check out past polls.

Notices?