Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

How to find the N largest values in an array?

by Zombie dubx56 (Initiate)
on Oct 03, 2001 at 22:57 UTC ( #116538=perlquestion: print w/ replies, xml ) 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.

Comment on How to find the N largest values in an array?
Download Code
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)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://116538]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (8)
As of 2014-09-18 10:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (111 votes), past polls