As the benchmarks show, your algorithm, is a good one. With a few tweaks to the implementation it runs faster still:
sub top_x {
my( $n, $aref ) = @_;
my @topN = (0)x$n--;
for my $val ( @$aref ) {
next if $topN[ $n ] > $val;
$topN[ $_ ] < $val
and splice( @topN, $_, 0, $val ), last
for 0 .. $n;
}
return @topN[ 0 .. $n ];
}
If this is more than an intellectual exercise, and you can handle Inline::C, then the same algorithm C-ified really flies:
Update: Correct the Inline::C implementation below to avoid calloc and allow me to free the temporary C array.
void topN( int n, AV*data ) {
int *topN;
int len = av_len( data );
int i, j, k;
Inline_Stack_Vars;
Newz( 1, topN, n + 1, int );
for( i = 0; i <= len; i++ ) {
int val = SvIV( *av_fetch( data, i, 0 ) );
for( j = 0; j < n; j++ ) {
if( topN[ j ] > val ) continue;
if( topN[ j ] < val ) {
for( k = n; k > j; k-- ) topN[ k ] = topN[ k-1 ];
topN[ j ] = val;
break;
}
}
}
Inline_Stack_Reset;
for( i = 0; i < n; i++ )
Inline_Stack_Push( sv_2mortal( newSViv( topN[ i ] ) ) );
Safefree( topN );
Inline_Stack_Done;
}
Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.
-
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.