Re^5: Better mousetrap (getting top N values from list X)

The code would need more work before it could go into List::Util

Agreed, but I did have a go at making topN() accept a comparator function, but the cost off calling back into Perl code for each comparison exacts a heavy performance penalty--to the point where it looses all benefit. Though it is possible that my fledgling XS/internals skills bore some of that cost.

The only way I see to avoid that, would be to have four separate routines, (say) highNn(); highNs(); lowNn(); lowNs();.

I think this is the route taken by sort, albeit that the "naming convention" (for backwards compatibiity?) is sort{$a<=>$b}(); thru sort{$bcmp$a}();

Since the basic algorithm needs only a size-N array, there ought to be some way to wrap this as a package that takes an arbitrary input set of unlimited size,...

Personally, I'm not very keen on that type of pseudo-OO wrapper around what is essentially a functional algorithm. Would the wrapper code accumulate a copy of everything passed or discard values that didn't make the cut?

If the former, unnecessary duplication of storage results. If the latter, I think I would prefer not to do a function call to reject individual values that don't make the cut. I'd code the accumlator scenario something like:

my @topN = topN( $n, \@data );

@topN = topN( $n, [ @topN, 
    grep{ chomp; $_ > $topN[ -1 ] } <>
] );
[download]

(BTW. I really wish that chomp returned the chomped value. It would make some constructs so much easier.)

or maybe

my @topN( $n, \@data );
my @batch;

while( not eof ARGV ) {
    for( my $i=0; $_ = <> and $i < $BATCHSIZE; $i++ ) {
        chomp;
        push @batch, $_;
    }
    @topN( $n, [ @topN, @batch ] );
}
[download]

Basically, I prefer to retain programmer choice in stuff like this--but there would be nothing to stop someone adding a wrapper around it, though four (type/direction) versions would probably be needed again.

Examine what is said, not who speaks.

Silence betokens consent.

Love the truth but pardon error.

Comment on Re^5: Better mousetrap (getting top N values from list X) Select or Download Code

Replies are listed 'Best First'.
Re^6: Better mousetrap (getting top N values from list X) by tall_man (Parson) on Feb 04, 2005 at 00:54 UTC
The wrapper would discard everything that didn't make the cut, so that only N values would be needed internally instead of `scalar(@X)` values. I can see why batching would be a good approach, though it wouldn't be too bad to allow single-valued insertions. I would just like an interface capable of handling multi-gig input streams without choking, and capable of reporting a running top-N at intervals within a loop without having to be reset.	[reply] [d/l]
Re^7: Better mousetrap (getting top N values from list X) by BrowserUk (Patriarch) on Feb 04, 2005 at 01:11 UTC
Understood. The reason for my reluctance to do things one at a time is because I saw the effects of doing a C to perl callback for the comparator. Just calling the comparator (without actually using it's return value) drops my topN() routine from first, to second last place in the benchmark. [ 1:01:43.25] P:\test>427029 -MAX=100 -N=10 10 from 100 (1 seconds) 100\|99\|98\|97\|96\|95\|94\|93\|92\|91 Rate Ari Buk LR BukLR perl C Ari 464/s -- -74% -83% -93% -98% -99% Buk 1768/s 281% -- -35% -74% -93% -97% LR 2731/s 488% 54% -- -60% -89% -95% BukLR 6876/s 1381% 289% 152% -- -72% -88% perl 24678/s 5217% 1296% 804% 259% -- -57% C 57443/s 12276% 3149% 2004% 735% 133% -- [ 1:02:07.47] P:\test>427029 -MAX=100 -N=10 10 from 100 (1 seconds) 100\|99\|98\|97\|96\|95\|94\|93\|92\|91 Rate Ari C Buk LR BukLR perl Ari 477/s -- -32% -72% -79% -92% -98% C 703/s 47% -- -59% -69% -88% -97% Buk 1729/s 262% 146% -- -24% -71% -93% LR 2266/s 375% 222% 31% -- -61% -91% BukLR 5881/s 1132% 737% 240% 159% -- -77% perl 25039/s 5146% 3463% 1348% 1005% 326% -- [download] There may be some fat that could be trimmed as I put the callback code in a separate C function (per the examples) in order to isolate all the stack manipulations. That could probably be inlined with care, but I also tried calling a dummy C-function and it is very clear that it is the callback to perl, not the call to the C function that is chewing all the time. Once you get into the C code, it's better to stay and do as much work as possible in one go. That said, I guess you could alway do the batching within the wrapping code also, which would make sense. Examine what is said, not who speaks. Silence betokens consent. Love the truth but pardon error.	[reply] [d/l]
Re^8: Better mousetrap (getting top N values from list X) by tall_man (Parson) on Feb 04, 2005 at 18:42 UTC
Out of curiousity, was your comparator of the `{$a <=> $b}` type, or did you pass parameters to it? It seems as if we could tap into sort's efficient comparator speed if we could use $a and $b from C code. Generic comparisons might be easier that way.	[reply] [d/l]
Re^9: Better mousetrap (getting top N values from list X) by BrowserUk (Patriarch) on Feb 04, 2005 at 21:23 UTC
Re^10: Better mousetrap (getting top N values from list X) by tall_man (Parson) on Feb 04, 2005 at 22:36 UTC
Some notes below your chosen depth have not been shown here


Pathologically Eclectic Rubbish Lister
	PerlMonks