Re^4: Finding the Shortest Element in an Array

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.

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

Comment on Re^4: Finding the Shortest Element in an Array Select or Download Code

Replies are listed 'Best First'.
Re^5: Finding the Shortest Element in an Array by Perl Mouse (Chaplain) on Oct 14, 2005 at 11:05 UTC
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:>`	[reply] [d/l]
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]