#! perl -slw
use strict;
use vars qw[ $SIZE $N $CHUNK ];

$SIZE  ||= 100_000;
$N     ||= 30;
$CHUNK ||= 100;

srand( 1 );

sub getTopN {
	my( $aref, $n ) = @_;
	my @top = @{ $aref }[ 0 .. ( $n - 1) ];

	for( my $p = $CHUNK; $p < @$aref; $p += $CHUNK ) {
		my $end = $p + $CHUNK < @$aref ? $p + $CHUNK : $#{ $aref };
		@top = (
			sort{ $b <=> $a } @top, @{ $aref }[ $p .. $end ]
		)[ 0 .. ( $n - 1 ) ];
	}
	return @top;
}
print scalar localtime;

my @numbers;
$#numbers = $SIZE;
$numbers[ $_ ] = int rand $SIZE for 0 .. $SIZE;

print scalar localtime;
print "@{[ getTopN( \@numbers, $N ) ]}";
print scalar localtime;

##</code><code>##

Array size | gen.(s) | sort(s)|	sort(s) | sort(s) | sort(s)
           |         |  (30)  |  (100)  | (1000)  | (10000)
-----------+---------+--------+---------+---------+-------
  100_000  |       1 |     4  |      3  |      2  |     2
1_000_000  |      12 |    55  |     38  |     33  |    36
2_000_000  |      29 |   138  |    102  |     88  |    93

##</code><code>##

P:\test>294065 -SIZE=100000 -N=30 -CHUNK=30
Thu Sep 25 10:42:39 2003
Thu Sep 25 10:42:40 2003
99996 99996 99996 99996 99996 99996 99993 99993 99993 99990 99990 99990 99990 99987 99987 99987
Thu Sep 25 10:42:44 2003

P:\test>294065 -SIZE=100000 -N=30 -CHUNK=100
Thu Sep 25 10:42:55 2003
Thu Sep 25 10:42:56 2003
99996 99996 99996 99996 99996 99996 99993 99993 99993 99990 99990 99990 99990 99987 99987 99987
Thu Sep 25 10:42:59 2003

P:\test>294065 -SIZE=100000 -N=30 -CHUNK=1000
Thu Sep 25 10:43:14 2003
Thu Sep 25 10:43:15 2003
99996 99996 99996 99996 99996 99996 99993 99993 99993 99990 99990 99990 99990 99987 99987 99987
Thu Sep 25 10:43:17 2003

P:\test>294065 -SIZE=100000 -N=30 -CHUNK=10000
Thu Sep 25 10:43:29 2003
Thu Sep 25 10:43:30 2003
99996 99996 99996 99996 99996 99996 99993 99993 99993 99990 99990 99990 99990 99987 99987 99987
Thu Sep 25 10:43:32 2003

P:\test>294065 -SIZE=1000000 -N=30 -CHUNK=30
Thu Sep 25 10:43:48 2003
Thu Sep 25 10:44:00 2003
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 99996
Thu Sep 25 10:44:55 2003

P:\test>294065 -SIZE=1000000 -N=30 -CHUNK=100
Thu Sep 25 10:45:13 2003
Thu Sep 25 10:45:25 2003
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 99996
Thu Sep 25 10:46:03 2003

P:\test>294065 -SIZE=1000000 -N=30 -CHUNK=1000
Thu Sep 25 10:46:15 2003
Thu Sep 25 10:46:26 2003
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 99996
Thu Sep 25 10:46:59 2003

P:\test>294065 -SIZE=1000000 -N=30 -CHUNK=10000
Thu Sep 25 10:47:20 2003
Thu Sep 25 10:47:31 2003
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 99996
Thu Sep 25 10:48:07 2003

P:\test>294065 -SIZE=2000000 -N=30 -CHUNK=30
Thu Sep 25 10:48:43 2003
Thu Sep 25 10:49:12 2003
1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938
Thu Sep 25 10:51:30 2003

P:\test>294065 -SIZE=2000000 -N=30 -CHUNK=100
Thu Sep 25 11:08:59 2003
Thu Sep 25 11:09:29 2003
1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938

Thu Sep 25 11:11:11 2003P:\test>294065 -SIZE=2000000 -N=30 -CHUNK=1000
Thu Sep 25 10:52:14 2003
Thu Sep 25 10:52:42 2003
1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938
Thu Sep 25 10:54:10 2003

P:\test>294065 -SIZE=2000000 -N=30 -CHUNK=10000
Thu Sep 25 10:55:13 2003
Thu Sep 25 10:55:41 2003
1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938 1999938
Thu Sep 25 10:57:14 2003