Re^4: pop sort strangeness

Just for reference, here's some timing results on my machine for the following code snippet...

#!/usr/bin/perl -w

#Initialization
@vals = reverse "a".."daaaa";

#O(NlogN)
my $max = pop @{[ sort @vals ]};

#O(N)
#my $max = $vals[0];
#$max = ( $_ gt $max ) ? $_ : $max foreach @vals;

$e=@vals;
print "elements=$e max=$max\n";
[download]

Commenting out everything but the initialization section (i.e. not finding any maximum at all), this snippet executes in about 4.4 seconds on my machine. Using the sort to find the max, it takes about 6.2 seconds. Finally, using the linear method, it executes in about 5.1 seconds. So, for the 1,846,183 elements in this example, the sort method is about 2.5 times slower (6.2-4.4)/(5.1-4.4) than the linear search method. But the test is still dominated by just generating the large array. So you might not notice the efficiency gain if your data set is smaller than 1.8 million elements.

-- All code is 100% tested and functional unless otherwise noted.

Comment on Re^4: pop sort strangeness Download Code

Replies are listed 'Best First'.
Re^5: pop sort strangeness by Eimi Metamorphoumai (Deacon) on Nov 17, 2004 at 20:06 UTC
Here are my results, first with your "a" .. "daaa", and then with a much smaller dataset ("a".."daa", only 2731 values), and finally with just "a" .. "aa" (27 values). #!/usr/bin/perl use strict; use warnings; use List::Util qw/ maxstr /; use Benchmark qw/ cmpthese /; my @vals = reverse "a" .. "daa"; cmpthese( -10, { sorting => sub {my $max = pop @{[sort @vals]}}, iterating => sub { my $max = $vals[0]; $max = ( $_ gt $max ) ? $_ : $max foreach @vals; }, list_util => sub {my $max = maxstr @vals} }); __END__ Rate sorting iterating list_utils sorting 0.659/s -- -42% -82% iterating 1.13/s 72% -- -69% list_util 3.67/s 458% 224% -- Rate sorting iterating list_utils sorting 537/s -- -32% -80% iterating 789/s 47% -- -70% list_util 2661/s 395% 237% -- Rate sorting iterating list_utils sorting 50180/s -- -25% -78% iterating 66991/s 34% -- -70% list_utils 225804/s 350% 237% -- [download] So in all cases, using the built in List::Util proceedure was quite a bit more than twice as fast as either of the others. And it's also much simpler to use, so it seems like something of a no-brainer to me.	[reply] [d/l]

Replies are listed 'Best First'.

Re^5: pop sort strangeness
by Eimi Metamorphoumai (Deacon) on Nov 17, 2004 at 20:06 UTC

#!/usr/bin/perl
use strict;
use warnings;

use List::Util qw/ maxstr /;
use Benchmark qw/ cmpthese /;

my @vals = reverse "a" .. "daa";

cmpthese( -10, {
    sorting => sub {my $max = pop @{[sort @vals]}},
    iterating => sub {
        my $max = $vals[0];
        $max = ( $_ gt $max ) ? $_ : $max foreach @vals;
    },
    list_util => sub {my $max = maxstr @vals}
    });
__END__
              Rate    sorting  iterating list_utils
sorting    0.659/s         --       -42%       -82%
iterating   1.13/s        72%         --       -69%
list_util   3.67/s       458%       224%         --

             Rate    sorting  iterating list_utils
sorting     537/s         --       -32%       -80%
iterating   789/s        47%         --       -70%
list_util  2661/s       395%       237%         --

               Rate    sorting  iterating list_utils
sorting     50180/s         --       -25%       -78%
iterating   66991/s        34%         --       -70%
list_utils 225804/s       350%       237%         --
[download]

[reply]
[d/l]