comment on

this is a small sub that can be used in situations where you have a large array to be sorted, but you really need only the first N elements of the sorted array.

you can think of it as something like the SQL SELECT * FROM foo ORDER BY bar LIMIT 10 (MySQL, Postgres) or SELECT TOP 10 * FROM foo ORDER BY bar (MSSQL).

of course, this has been thought of as an optimization, but to deserve the name of optimization it should really be implemented in C (XS/Inline/whatever you want). it could still perform quickier than a full sort, I suspect, particularly if your comparison function is very expensive.

SYNOPSIS

my @topten = sort_top(10, sub { $a <=> $b }, @huge_array);
[download]

sub sort_top {
    my($top, $func, @arr) = @_;
    my @top = sort $func @arr[0..$top-1];
    for my $i ($top..$#arr) {    
        my $x = -1;
        for (my $t = $#top; $t >= 0; $t--) {
            local ($a, $b) = ($arr[$i], $top[$t]);
            last if($func->() == 1);
            $x = $t;
        }
        if($x != -1) {
            splice(@top, $x, 0, $arr[$i]);
            pop(@top);
        }    
    }    
    return @top;    
}
[download]

In reply to sort_top by dada

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.


Don't ask to ask, just ask
	PerlMonks