P is for Practical PerlMonks

### How can one find five max values and five min values with positions in descending and ascending order from arrays?

by supriyoch_2008 (Scribe)
 on Apr 26, 2013 at 04:45 UTC Need Help??
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
• Comment on How can one find five max values and five min values with positions in descending and ascending order from arrays?

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 (Archbishop) 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 (Canon) 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 (Prior) 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 (Priest) 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 (Chancellor) 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 (Priest) 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

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1030762]
Approved by 2teez
help
Chatterbox?
 [GotToBTru]: 99% of all deaths take place within 24 hours of ingesting di-hydrogen monoxide [GotToBTru]: time for some C8H10N4O2 for me [ambrus]: GotToBTru: wait, you tell only the atom totals of what you want? Is that like ordering food in a restaurant by telling only the nutrient amounts you need, or [ambrus]: like when a medieval scientist supposedly proves his priority inventing something by having previously published an anagram of a thousand letters long summary of the invention?

How do I use this? | Other CB clients
Other Users?
As of 2016-12-06 13:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
On a regular basis, I'm most likely to spy upon:

Results (104 votes). Check out past polls.