http://www.perlmonks.org?node_id=1030762

supriyoch_2008 has asked for the wisdom of the Perl Monks concerning the following question:

Hi Perlmonks,

I have two arrays i.e. @x and @y containing eight names and eight numerical values, respectively. Each name in @x corresponds to the particular value in @y at the specific position. I am interested in finding out five maximum values with positions in @y in descending order and five minimum values with positions in @y in ascending order. I am at my wit's end to find it. I can find out only the maximum and minimum value from the array @y. I seek the wisdom of perlmonks in this matter. I have given the two arrays below:

@x = qw/c d e f k l m n/; @y = qw/4 6 5 2 9 7 8 3/;

The desired results should look something like:

Max values (only 5) in descending order with positions in name array: 9 corresponds to k at position 4 8 corresponds to m at position 6 7 corresponds to l at position 5 6 corresponds to d at position 1 5 corresponds to e at position 2 Min values (only 5) in ascending order with positions in name array: 2 corresponds to f at position 3 3 corresponds to n at position 7 4 corresponds to c at position 0 5 corresponds to e at position 2 6 corresponds to d at position 1

Replies are listed 'Best First'.
Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by davido (Cardinal) on Apr 26, 2013 at 05:53 UTC

    If your data set isn't too large, just sort. If it is large, do a partial sort. Here's an example of each method:

    use strict; use warnings; my @x = qw( c d e f k l m n ); my @y = qw( 4 6 5 2 9 7 8 3 ); # Full sort method: -------------------------------------------------- +- my @sorted_idx = sort { $y[$a] <=> $y[$b] } 0 .. $#y; print "The five highest valued names:\n"; print_range( reverse @sorted_idx [ $#sorted_idx-4 .. $#sorted_idx ] ); print "The five lowest valued names:\n"; print_range( @sorted_idx[ 0 .. 4 ] ); # Partial sort method: ----------------------------------------------- +-- use Sort::Key::Top qw( keytopsort ); print "The five highest valued names:\n"; print_range( reverse keytopsort { $y[$_] } -5 => 0 .. $#y ); print "The five lowest valued named:\n"; print_range( keytopsort { $y[$_] } 5 => 0 .. $#y ); # Helper sub: -------------------------------------------------------- +-- sub print_range { my @indices = @_; print "\t$x[$_] => $y[$_] at position $_\n" for @indices; }

    It's my understanding that the partial sort method (Sort::Key::Top) implements the "Linear General Selection Algorithm" (Wikipedia article), which provides a very efficient solution.

    Another option (that is also supported by CPAN) is to build two heaps; one for mins, and one for max's, and then pop the first five elements off of each.

    Either of the two solutions I provided will produce the following output:

    The five highest valued names: k => 9 at position 4 m => 8 at position 6 l => 7 at position 5 d => 6 at position 1 e => 5 at position 2 The five lowest valued names: f => 2 at position 3 n => 3 at position 7 c => 4 at position 0 e => 5 at position 2 d => 6 at position 1

    Dave

      Indeed, linear selection is significantly faster (O(n)) than sorting for large lists of values.

      I'll take this opportunity to plug Sort::Key::Top::PP, my pure Perl implementation of some of the ideas in Sort::Key::Top. It uses a lot of trickery and some ugly looking code to provide very fast results. (Much faster that code you might write yourself if you were caring about its aesthetics.)

      package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name

      Hi davido,

      Thanks a lot. The code has worked and solved my problem. I'm sorry for late reply.

      With deep regards,

Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by kcott (Archbishop) on Apr 26, 2013 at 05:59 UTC

    G'day supriyoch_2008,

    You should take a look at sort. Is there something you don't understand about ascending and descending sorts? This technique worked for me:

    $ perl -Mstrict -Mwarnings -E ' my @x = qw/c d e f k l m n/; my @y = qw/4 6 5 2 9 7 8 3/; my @sorted_y = sort { $a <=> $b } @y; my %yx_map = map { $y[$_] => [$x[$_], $_] } 0 .. $#y; say q{Max values:}; say "$_ = $yx_map{$_}[0] at $yx_map{$_}[1]" for reverse @sorted_y[ +-5..-1]; say q{Min values:}; say "$_ = $yx_map{$_}[0] at $yx_map{$_}[1]" for @sorted_y[0..4]; ' Max values: 9 = k at 4 8 = m at 6 7 = l at 5 6 = d at 1 5 = e at 2 Min values: 2 = f at 3 3 = n at 7 4 = c at 0 5 = e at 2 6 = d at 1

    -- Ken

Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by hdb (Monsignor) on Apr 26, 2013 at 05:55 UTC

    First of all, the question is whether x or y can be assumed to have unique values. Either of the two can then be used as keys to a hash to store the association of the two arrays. In this case, the task is straightforward.

    In the general case, one needs to introduce the position as the key to a hash that stores x and y. One can then sort the keys with respect to y. Here is how it could look like:

    use strict; use warnings; # initial data my @x = qw/c d e f k l m n/; my @y = qw/4 6 5 2 9 7 8 3/; # store in hash to keep association between x and y after sorting my %data; for my $i (0..@x-1) { $data{$i}{x} = $x[$i]; # store x corresponding to position $i $data{$i}{y} = $y[$i]; # store y corresponding to position $i } # sort positions with respect to y my @sorted = sort { $data{$a}{y} <=> $data{$b}{y} } keys %data; print "Sorted data:\n"; for my $i (@sorted) { print "$data{$i}{y} corresponds to $data{$i}{x} at position $i +\n"; }

    To print the highest and lowest 5 should now be simple...

      Hi hdb,

      Thanks for the code. It has solved my problem. Sorry for late reply.

      With deep regards,

Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by Jenda (Abbot) on Apr 26, 2013 at 15:01 UTC
    I have two arrays i.e. @x and @y containing eight names and eight numerical values, respectively. Each name in @x corresponds to the particular value in @y at the specific position.

    DON'T!

    This is a bad datastructure decision and this task is just one of the many that are harder than necessary due to this. Do store the data as an array of arrays or array of hashes!

    Jenda
    Enoch was right!
    Enjoy the last years of Rome.

Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by Random_Walk (Prior) on Apr 26, 2013 at 09:28 UTC

    Keeping it simple. If you really only need the output you gave

    #!/usr/bin/perl use strict; use warnings; use 5.010; use Data::Dumper; use constant IWANT => 5; my @names = qw/c d e f k l m n o p q r s t u/; my @vals = qw/4 6 5 2 9 7 8 3 3 5 8 8 2 4 12/; my @data; my $pos = 1; for my $val (@vals) { # Build a table my $name = shift @names; my $rec = sprintf "%2d corresponds to %s at pos %2d", $val, $name +, $pos++; push @data, $rec; } say "\nSmall to Big"; @data = sort @data; for (0..IWANT-1) { say $data[$_]; } say "\nBig to Small"; for (1..IWANT) { say $data[-$_]; }

    Cheers,
    R.

    Pereant, qui ante nos nostra dixerunt!
Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by 2teez (Vicar) on Apr 26, 2013 at 04:58 UTC

    the array "@x" doesn't contain names, they are simply alphabets. Please clarify.

    If you tell me, I'll forget.
    If you show me, I'll remember.
    if you involve me, I'll understand.
    --- Author unknown to me
Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by Rahul6990 (Beadle) on Apr 26, 2013 at 06:05 UTC
    Hi supriyoch_2008,

    Try the below steps:
    1. Create hash with first array element as key and second array element as value.
    2. Sort the hash on the basis of its value in ascending order and print top 5 key , value pair.
    3. Sort the hash on the basis of its value in descending order and print top 5 key , value pair.

    Below link will provide all the required things on Hashes Hash

    In case you are stuck somewhere we are happy to help you.

    Happy Programming....
Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by LanX (Saint) on Apr 26, 2013 at 08:34 UTC
    What did you try?

    DB<103> @h{@y}=@x => ("c", "d", "e", "f", "k", "l", "m", "n") DB<104> @h{(sort @y)[0..4]} => ("f", "n", "c", "e", "d") DB<105> @h{(sort @y)[-5..-1]} => ("e", "d", "l", "m", "k")

    Cheers Rolf

    ( addicted to the Perl Programming Language)

Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by TJPride (Pilgrim) on Apr 26, 2013 at 13:47 UTC
    Unless your arrays are hugely massive, something like this:
    use strict; use warnings; my @x = qw/c d e f k l m n/; my @y = qw/4 6 5 2 9 7 8 3/; ### Combine arrays for easy sorting my @z; push @z, [$_, $x[$_], $y[$_]] for 0..$#x; print "Max values (only 5) in descending order with positions in name +array:\n"; print "$_->[2] corresponds to $_->[1] at position $_->[0]\n" for (sort { $b->[2] <=> $a->[2] } @z)[0..4]; print "\n"; print "Min values (only 5) in ascending order with positions in name a +rray:\n"; print "$_->[2] corresponds to $_->[1] at position $_->[0]\n" for (sort { $a->[2] <=> $b->[2] } @z)[0..4];
Re: How can one find five max values and five min values with positions in descending and ascending order from arrays?
by BillKSmith (Monsignor) on Apr 26, 2013 at 13:27 UTC
    Often, clarity is more important than efficiency. Sort the indicies into the required order. Print the data from both arrays corresponding to the first five indicies and to last five indicies. The Schwartzian Transformation is a well-known idiom which could be used to reduce the inefficiency.
    Bill