Re^5: Finding the Shortest Element in an Array

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%     --
[download]

Perl --((8:>*

Comment on Re^5: Finding the Shortest Element in an Array Download Code

Replies are listed 'Best First'.
Re^6: Finding the Shortest Element in an Array by sauoq (Abbot) on Oct 14, 2005 at 15:30 UTC
However, all the sorts lose very badly to the linear solutions. Yeah... that's expected, of course. And the longer the list gets, the worse the beating the O(n) solutions will give to the O(n log n) sorts too. That's the important fact because, sometimes with small datasets, benchmarks will show the worse algorithm outperforming the better one. But, when the datasets get larger, the better algorithm inevitably wins. The moral being that analysis is better than benchmarking. -sauoq "My two cents aren't worth a dime.";	[reply]

Replies are listed 'Best First'.

Re^6: Finding the Shortest Element in an Array
by sauoq (Abbot) on Oct 14, 2005 at 15:30 UTC

However, all the sorts lose very badly to the linear solutions.

Yeah... that's expected, of course. And the longer the list gets, the worse the beating the O(n) solutions will give to the O(n log n) sorts too. That's the important fact because, sometimes with small datasets, benchmarks will show the worse algorithm outperforming the better one. But, when the datasets get larger, the better algorithm inevitably wins. The moral being that analysis is better than benchmarking.

-sauoq
"My two cents aren't worth a dime.";

[reply]