Indeed. ST loses badly to just a plain sort. To my surprise, a GRT loses to the plain sort as well, even with an array with 100 thousand elements. However, all the sorts lose very badly to the linear solutions. Here's a benchmark:
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw 'cmpthese';
use List::Util 'reduce';
my $size = shift || 10_000;
my $max_l = shift || 50;
our @data = map {"1" x (1 + rand $max_l)} 1 .. $size;
our ($p, $s, $g, $r, $f);
cmpthese -5, {
plain => '$p = (sort {length($a) <=> length($b)} @data) [0]',
ST => '$s = (map {$_->[0]}
sort {$a->[1] <=> $b->[1]}
map {[$_, length]} @data) [0]',
GRT => '$g = (map {substr $_, 4}
sort
map {pack "NA*", length($_), $_} @data) [0]',
reduce => '$r = reduce {length($a) < length($b) ? $a : $b} @data
+',
for => '$f = $data[0];
for (@data) {$f = $_ if length($_) < length($f)}',
};
die unless $p eq $s && $p eq $g && $p eq $r && $p eq $f;
__END__
Rate ST GRT plain for reduce
ST 10.6/s -- -57% -66% -95% -97%
GRT 24.5/s 132% -- -22% -89% -92%
plain 31.3/s 197% 28% -- -86% -90%
for 222/s 2004% 805% 609% -- -28%
reduce 308/s 2817% 1156% 883% 39% --
|