Re^3: Finding the Shortest Element in an Array

[jeffa]

Perhaps sort was chosen because using sort is easy on the person writing the code. That was the first thing that came to my mind -- just sort the list based on length, but i see no reason to use a Schwartzian Transform here. This should suffice, and while it may take longer and use more memory, it sure looks neat:

@array = sort { length($a) <=> length($b) } @array;

Code like that reminds me of my days painting dorm rooms. My boss would tell me "Let the brush do the work, not you." And yes, that would include using List::Util, FWIW.

[sauoq]

While I don't care for the idea of using sort for this, if you are going to use it, doing it like you did and avoiding the ST probably makes a lot of sense. It should take less memory, not more. And, since length() is very fast it probably won't lose by much on performance either (it might even win.) And, you just can't beat the clarity of the code.

[Perl Mouse]

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%     --

[sauoq]

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.