#!/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
    };
}
[download]