Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
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 exploiting the Monastery: (11)
As of 2015-07-02 10:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (33 votes), past polls