Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

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.


In reply to Re^3: Better mousetrap (getting top N values from list X) by Aristotle
in thread Better mousetrap (getting top N values from list X) by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • 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.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chilling in the Monastery: (4)
As of 2024-03-29 07:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found