#!/usr/bin/env perl
use warnings;
use strict;
use Benchmark 'cmpthese';
use List::Util 'shuffle';
# to run tests first: $ DO_CHECK=1 perl sort.pl && perl sort.pl
use constant DO_CHECK => !!$ENV{DO_CHECK};
use if DO_CHECK, 'Data::Compare', qw/Compare/;
srand 123;
my @tests = ( # first item here will be used in benchmark by default
[ [shuffle -52,-50..50,52,0], [-52,-50..-1,0,0..50,52], 'random'],
[ [-52,-50..50,52,0], [-52,-50..-1,0,0..50,52], 'ordered' ],
[ [shuffle -50..-1,1..50], [-50..-1,1..50], 'no zero'],
[ [shuffle -102,-100..-1], [-102,-100..-1], 'negative only' ],
[ [shuffle -102,-100..0], [-102,-100..-1,0],
'negative only with zero'],
[ [shuffle 0..100,102],[0..100,102],'positive only with zero' ],
[ [shuffle 1..100,102],[1..100,102],'positive only without zero'],
[ [shuffle((-4..4)x10)], [ map {($_)x10} -4..4 ], 'many dupes' ],
);
for my $t (@tests) {
print "# ### Benchmarking with data set: $$t[2] ###\n";
cmpthese(DO_CHECK ? 1 : -2, {
sort => sub {
my @list = @{$$t[0]};
@list = sort {$a<=>$b} @list;
Compare(\@list,$$t[1]) or die "<@list>" if DO_CHECK;
},
qsort => sub {
use List::MoreUtils 'qsort';
my @list = @{$$t[0]};
qsort {$a<=>$b} @list;
Compare(\@list,$$t[1]) or die "<@list>" if DO_CHECK;
},
custom => sub {
my @list = @{$$t[0]};
QSort(@list);
Compare(\@list,$$t[1]) or die "<@list>" if DO_CHECK;
},
});
}
sub QSort {
@_ or return;
my $First = 0;
my $Last = @_ - 1;
my @QStack;
my $StackPtr = 0;
my $temp;
my $i;
my $j;
for (;;) {
do {
$temp = $_[int(($Last + $First) / 2)];
$i = $First;
$j = $Last;
do {
while ($_[$i] < $temp) { $i++; }
while ($_[$j] > $temp) { $j--; }
if ($i < $j) { @_[$i, $j] = @_[$j, $i]; }
if ($i <= $j) { $i++; $j--; }
} while ($i <= $j);
if ($i < $Last) {
$QStack[$StackPtr++] = $i;
$QStack[$StackPtr++] = $Last;
}
$Last = $j;
} while ($First < $Last);
$StackPtr or return;
$Last = $QStack[--$StackPtr];
$First = $QStack[--$StackPtr];
}
}
__END__
# ### Benchmarking with data set: random ###
Rate custom qsort sort
custom 10697/s -- -83% -95%
qsort 62127/s 481% -- -70%
sort 209474/s 1858% 237% --
# ### Benchmarking with data set: ordered ###
Rate custom qsort sort
custom 16593/s -- -72% -96%
qsort 59065/s 256% -- -84%
sort 376539/s 2169% 537% --
# ### Benchmarking with data set: no zero ###
Rate custom qsort sort
custom 10808/s -- -83% -95%
qsort 65159/s 503% -- -69%
sort 213372/s 1874% 227% --
# ### Benchmarking with data set: negative only ###
Rate custom qsort sort
custom 11058/s -- -82% -95%
qsort 62126/s 462% -- -72%
sort 219498/s 1885% 253% --
# ### Benchmarking with data set: negative only with zero ###
Rate custom qsort sort
custom 11441/s -- -82% -95%
qsort 63315/s 453% -- -71%
sort 217417/s 1800% 243% --
# ### Benchmarking with data set: positive only with zero ###
Rate custom qsort sort
custom 10453/s -- -83% -95%
qsort 60424/s 478% -- -71%
sort 212006/s 1928% 251% --
# ### Benchmarking with data set: positive only without zero ###
Rate custom qsort sort
custom 10900/s -- -83% -95%
qsort 65471/s 501% -- -70%
sort 216391/s 1885% 231% --
# ### Benchmarking with data set: many dupes ###
Rate custom qsort sort
custom 13091/s -- -89% -95%
qsort 123098/s 840% -- -48%
sort 238432/s 1721% 94% --