Why not post it in the thread? Here's an adapted bench with a version of my code modified slightly to be callable like the others:
#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( reduce );
use Benchmark qw( cmpthese );
my %code = (
limbic => sub {
my ($x, $list) = @_;
$x--;
my @top;
$#top = $x;
for my $item ( @$list ) {
next if defined $top[ -1 ] && $item <= $top[ -1 ];
for my $id ( 0 .. $#top ) {
$top[ $id ] = $item and last if ! defined $top[ $id ];
if ( $item > $top[ $id ] ) {
@top[ $id .. $#top ] = ($item, @top[ $id .. $#top
+- 1]);
last;
}
}
}
return @top;
},
browseruk => sub {
my( $n, $aref ) = @_;
my @topN;
push @topN, reduce{
$a > $b && (!@topN || $a < $topN[ -1 ] )
? $a : ( !@topN || $b < $topN[ -1 ] )
? $b : $a;
} @$aref for 1 .. $n;
return @topN;
},
aristotle => sub {
my ( $n, $list ) = @_;
my @top = @$list[ 0 .. $n - 1 ];
@top = ( sort { $a <=> $b } $_, @top )[ 1 .. $n ] for @$list[
+$n .. $#$list ];
return @top;
},
);
my @bench = (
[ qw/ 10 5 / ],
[ qw/ 100 5 / ],
[ qw/ 1000 5 / ],
[ qw/ 10000 5 / ],
[ qw/ 100000 5 / ],
[ qw/ 100 50 / ],
[ qw/ 1000 50 / ],
[ qw/ 10000 50 / ],
[ qw/ 100000 50 / ],
[ qw/ 1000 500 / ],
[ qw/ 10000 500 / ],
[ qw/ 100000 500 / ],
);
$|++;
while( @bench ) {
my ( $max, $n ) = @{ shift @bench };
my $duration = sprintf "%.2g", ( log( $max ) / log( 20 ) ) ** 2;
print "\nLooking for top $n in $max (running for $duration CPU sec
+s)\n";
my @values = 1 .. $max;
my @top = ( sort { $a <=> $b } @values )[ @values - $n .. $#values
+ ];
for( keys %code ) {
my @result = sort { $a <=> $b } $code{ $_ }->( $n, \@values );
die "$_ not ok: [@result] ne [@top]\n" if "@result" ne "@top";
}
cmpthese -$duration => {
map { my $x = $code{ $_ }; $_ => sub { my @x = $x->( $n, \@val
+ues ) } } keys %code
};
}
It is interesting to see that my code wins hands down when N/MAX is close to 1. Even when the ratio of N/MAX shrinks, my code loses a lot of ground but keeps beating Limbic's proposition. None of this matters much though since for large MAX, all of the solutions perform very similarly, even if the trends remain clear.
So out of curiosity I added the following bit to the code:
baseline => sub {
my ( $n, $list ) = @_;
return ( sort { $a <=> $b } @$list )[ @$list - $n .. $#$list ]
+;
},
Well, I'll just say let's pack the bags and go home folks. Nothing to see here, move along. As I said: clever Perl code vs builtin: clever Perl code loses. Grossly disproportionately, in fact.
(Spoiler for anyone who doesn't care to run the benchmarks: in all cases the baseline sort version runs hundreds to thousands of times faster than the other solutions.)
Makeshifts last the longest.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.