Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

largest number inside array/hash

by Anonymous Monk
on Apr 06, 2004 at 18:28 UTC ( #343060=perlquestion: print w/replies, xml ) Need Help??

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

What's the easiest way to scan through an array or hash built with numbers (in a hash, the keys are numbers) and determine what the highest number is? For unique keys (I know other people will suggest other methods but this is what I chose and I like this method), I used numbers and to be sure I never accidently screw up I need to make sure it's +1 the greatest number it finds.

Can't just $num++ because I delete some hash keys/array values and doing so, the count would mess up and I'd overwrite hash keys. So I need to know the largest number in a hash (would be nice to know how this would work for an array as well, but it's probably the same thing) so I can add to it.

Thanks wise monks.

Replies are listed 'Best First'.
Re: largest number inside array/hash
by Art_XIV (Hermit) on Apr 06, 2004 at 18:52 UTC

    List::Util is probably the easiest for simple lists:

    use strict; use warnings; use List::Util qw(max); my @list = qw(1 99 33 2 1024 13); print max(@list) . "\n"

    Update: Note that List::Util could still be useful for hashes via the keys and values functions.

    Hanlon's Razor - "Never attribute to malice that which can be adequately explained by stupidity"
Re: largest number inside array/hash
by eric256 (Parson) on Apr 06, 2004 at 18:37 UTC

    You could always just sort it and then take the highest one. I'm not sure how that compares speed wise with just scanning threw 1 by 1. Of course you could just keep a $counter and increment it when adding and not decrement it when removing. Then there is no need to find the highest because you remember it.

    my $highest; for (@array) { # or keys %hash $highest = $_ if $_ > $highest; }

    ___________
    Eric Hodges

      I did some quick playing with the methods shown here just to get an idea of speed. Before now i've never looked at List::Util because I could do it all myself but now I think I see the light. It provides an astounding speed bonus.

      use strict; use warnings; use Benchmark ; use List::Util qw(max shuffle); my @a = (1..500_000); my @b = shuffle (1..500_000); my $greatest; timethese(25, { 'sort_shuffled' => sub {($greatest)=sort{$b<=>$a}@b;}, 'grep_shuffled' => sub { grep($greatest=($_>$greatest)?$_:$greatest,@b); }, 'for_shuffled' => sub { $greatest = 0; for (@b) { $greatest = $_ if $_ > $greatest; } }, 'max_shuffled' => sub { max(@b) }, 'sort_inorder' => sub {($greatest)=sort{$b<=>$a}@a;}, 'grep_inorder' => sub { grep($greatest=($_>$greatest)?$_:$greatest,@a); }, 'for_inorder' => sub { $greatest = 0; for (@a) { $greatest = $_ if $_ > $greatest; } }, 'max_inorder' => sub { max(@a) } }); __DATA__ Benchmark: timing 25 iterations of for_inorder, for_shuffled, grep_ino +rder, grep_shuffled, max_inord er, max_shuffled, sort_inorder, sort_shuffled... for_inorder: 5 wallclock secs ( 5.17 usr + 0.00 sys = 5.17 CPU) @ +4.83/s (n=25) for_shuffled: 4 wallclock secs ( 3.55 usr + 0.00 sys = 3.55 CPU) @ + 7.05/s (n=25) grep_inorder: 4 wallclock secs ( 3.75 usr + 0.00 sys = 3.75 CPU) @ + 6.67/s (n=25) grep_shuffled: 4 wallclock secs ( 3.70 usr + 0.00 sys = 3.70 CPU) @ + 6.75/s (n=25) max_inorder: 1 wallclock secs ( 0.89 usr + 0.00 sys = 0.89 CPU) @ 2 +8.09/s (n=25) max_shuffled: 1 wallclock secs ( 0.91 usr + 0.00 sys = 0.91 CPU) @ +27.59/s (n=25) sort_inorder: 1 wallclock secs ( 1.73 usr + 0.02 sys = 1.75 CPU) @ +14.28/s (n=25) sort_shuffled: 36 wallclock secs (34.34 usr + 0.05 sys = 34.39 CPU) @ + 0.73/s (n=25)

      I was curious if anyone could explain why grep is so much faster thant the for? Ohh and how do people do those cool comparison benchmarks with the chart?


      ___________
      Eric Hodges
        Ohh and how do people do those cool comparison benchmarks with the chart?
        Use "cmpthese" instead of "timethese".

        MJD says "you can't just make shit up and expect the computer to know what you mean, retardo!"
        I run a Win32 PPM repository for perl 5.6.x and 5.8.x -- I take requests (README).
        ** The third rule of perl club is a statement of fact: pod is sexy.

Re: largest number inside array/hash
by DamnDirtyApe (Curate) on Apr 06, 2004 at 18:38 UTC
    my %hash = ( 12 => undef, 18 => undef, 6 => undef, 22 => undef, 28 => undef, 16 => undef ); printf "Max value is %d.$/", ( sort {$b <=> $a} keys %hash )[0];

    _______________
    DamnDirtyApe
    Those who know that they are profound strive for clarity. Those who
    would like to seem profound to the crowd strive for obscurity.
                --Friedrich Nietzsche
Re: largest number inside array/hash
by insensate (Hermit) on Apr 06, 2004 at 18:40 UTC
    @alist=qw/1 50 2 658 74 256 21/; ($greatest) = sort {$b<=>$a}@alist; print $greatest;
    Will also work for sort {$b<=>$a} keys %myhash

    addendum:

    For extremely large sets, matija is absolutely right:

    use Benchmark ; my @a = (1..500000); my $greatest; timethese(5, { 'sort' => sub {($greatest)=sort{$b<=>$a}@a;}, 'grep' => sub { grep($greatest=($_>$greatest)?$_:$greatest,@a); }, }); Benchmark: timing 5 iterations of grep, sort... grep: 3 wallclock secs ( 3.36 usr + 0.02 sys = 3.38 CPU) @ 1 +.48/s (n=5) sort: 13 wallclock secs (12.22 usr + 0.04 sys = 12.26 CPU) @ 0 +.41/s (n=5)
Re: largest number inside array/hash
by matija (Priest) on Apr 06, 2004 at 19:01 UTC
    for an array, i'd use
    my $max; grep($max=($_>$max)?$_:$max,@arr);
    For searching among the keys of a hash, just replace @arr with keys %hash.

    Sorting a whole array just to find the largest element is waay overkill - you do too many comparisons, and you have to move the elements around. It doesn't really matter for arrays that have ten or so elements, but as soon as you get to thousands, you will start noticing the difference.

      This does not contain any data, it doesn't store anything in $max and I know the hash works because I'm using it elsewhere.
      my $max; grep($max=($_>$max)?$_:$max,keys %files); print $max;
        I really, really doubt that.

        Here is the code I tested with, and it's output:

        #!/usr/bin/perl my %files=%{{1=>"a", 2=>"b", 34=>"c", 5=>"d", 6=>"e", 7=>"f", 8=>"g", +9=>"h"}}; my $max; print join(" ",keys %files),"\n"; grep($max=($_>$max)?$_:$max,keys %files); print "<$max>\n";
        Output:
        perl /tmp/foo 6 8 1 34 7 9 2 5 <34>
        I don't know what you did to mess up, but it does so contain data, and stores the max.

        My guess is that if you try it with your files, you'll find it either works, or your hash doesn't look the way you expect. (Hint: try to output it with Data::Dumper

Re: largest number inside array/hash
by blue_cowdawg (Monsignor) on Apr 06, 2004 at 19:13 UTC

    And in the spirit of TIMTOWTDI:

    : : my $max=0; map { $max=($max < $_ ? $_ : $max )} @array_of_nums; : : or a hash... my $kmax=0; map { $kmax =($kmax < $_ ? $_ : $kmax) } keys %hash_nums;

      my $max=0;

      That's the classic max (or min) implementation error. What if all numbers are negative?

      $ perl -e'@a=qw(-1 -2 -3 -4 -5); $max=0; printf "Answer allegedly is %d\n",map { $max=($max < $_ ? $ +_ : $max )} @a;' Answer allegedly is 0 $ perl -e'@a=qw(-1 -2 -3 -4 -5); $max=$a[0]; # Or shift @a, if you can be destructive printf "Answer allegedly is %d\n",map { $max=($max < $_ ? $ +_ : $max )} @a;' Answer is -1

      Mike
Re: largest number inside array/hash
by DigitalKitty (Parson) on Apr 06, 2004 at 21:47 UTC
    Hi Anonymous Monk.

    In an attempt to display the 'syntactically rich' nature of the perl language, I have taken the liberty of including yet another array oriented solution:
    #!/usr/bin/perl -w use strict; my @array = ( 33, 56, 3, 2, 67, 101, 218, 4, 17 ); my @nums = sort { $a <=> $b } @array; print "The largest number is: $nums[$#nums]\n";

    Output:
    C:\>perl pg8.pl The largest number is: 218

    C:\>

    Hope this helps,
    -Katie

      Think back to second year of college, when you took that Algorithms course.

      A good sort such as quick sort is O( N logN ), poor ones such as bubble sort are O( N^2 ). A max() function requires a single pass through the list, and so is O( N ). It would be silly to do N log N - N ( i.e. N (log N - 1) ) operations more than you need to.

      --
      TTTATCGGTCGTTATATAGATGTTTGCA

        In practice, on small data sets, the penalty is a factor of 10 or so. Which is similar to the penalty from using Perl. If you can get a good constant, the log(n) might be paid for. (Real example. Wavelet algorithms tend to be O(n) while the FFT is O(n*log(n)). But the FFT has a better constant.) At some point worrying about how the computer spends a millisecond of time itself becomes silly.

        Me, I tend to treat logarithmic factors as noise unless I'm trying to squeeze performance. The difference between linear and quadratic I care about. O(n) vs O(n*log(n)) I don't. I know them, I just don't care much.

      Hi Nice elegant solution. but i guess this would work too
      #!/usr/bin/perl -w use strict; my @array = ( 33, 56, 3, 2, 67, 101, 218, 4, 17 ); my @nums = sort { $b <=> $a } @array; print "The largest number is: $nums[0]\n";

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (8)
As of 2021-04-12 12:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?