Re: length() and the Schwartzian transform

Looks like you're right - plain sort beats the heck out of ST in this case (and would do the same to GRT, I'm sure) - length is just too trivial.

Although as the num-* cases below show, it turns out that length is more expensive for data that isn't pre-stringified, at least on the perl 5.14.2 I tested.

#!/usr/bin/perl

use strict;
use warnings;
use Benchmark qw(:all :hireswallclock);

foreach my $arraySize(10,100,1_000,10_000,100_000) {
    my @numdata=map rand, 0..$arraySize;
    my @strdata=map {sprintf "%d",$_} @numdata;

    print "========== ARRAY SIZE: $arraySize\n";

    cmpthese(
            -1,
            {
                'str-ST' => sub {
                    my @arr = @strdata;
                    @arr = map { $_->[0] }
                           sort {$a->[1]<=>$b->[1]}
                           map { [$_, length($_)]}
                           @arr;
                },

                'str-sort' => sub {
                    my @arr = @strdata;
                    @arr = sort {length($a) <=> length($b)} @arr;
                },

                'num-ST' => sub {
                    my @arr = @numdata;
                    @arr = map { $_->[0] }
                           sort {$a->[1]<=>$b->[1]}
                           map { [$_, length($_)]}
                           @arr;
                },

                'num-sort' => sub {
                    my @arr = @numdata;
                    @arr = sort {length($a) <=> length($b)} @arr;
                },

            }
        );
}
[download]

Results:

$ perl benchmark-sort.pl
========== ARRAY SIZE: 10
            Rate   num-ST num-sort   str-ST str-sort
num-ST    5119/s       --      -9%     -77%     -90%
num-sort  5598/s       9%       --     -75%     -89%
str-ST   22719/s     344%     306%       --     -55%
str-sort 50539/s     887%     803%     122%       --
========== ARRAY SIZE: 100
           Rate   num-ST num-sort   str-ST str-sort
num-ST    534/s       --     -13%     -82%     -92%
num-sort  615/s      15%       --     -79%     -91%
str-ST   2904/s     444%     372%       --     -58%
str-sort 6854/s    1184%    1014%     136%       --
========== ARRAY SIZE: 1000
           Rate   num-ST num-sort   str-ST str-sort
num-ST   51.8/s       --     -16%     -82%     -93%
num-sort 61.4/s      18%       --     -79%     -92%
str-ST    290/s     460%     373%       --     -61%
str-sort  741/s    1330%    1107%     155%       --
========== ARRAY SIZE: 10000
           Rate   num-ST num-sort   str-ST str-sort
num-ST   5.13/s       --     -16%     -82%     -93%
num-sort 6.15/s      20%       --     -78%     -92%
str-ST   28.2/s     449%     358%       --     -62%
str-sort 73.7/s    1336%    1099%     162%       --
========== ARRAY SIZE: 100000
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
            (warning: too few iterations for a reliable count)
         s/iter   num-ST num-sort   str-ST str-sort
num-ST     1.93       --     -13%     -81%     -93%
num-sort   1.68      15%       --     -78%     -92%
str-ST    0.364     432%     363%       --     -61%
str-sort  0.142    1258%    1083%     155%       --

Mike

Comment on Re: length() and the Schwartzian transform Download Code

Replies are listed 'Best First'.
Re^2: length() and the Schwartzian transform by tobyink (Canon) on Feb 27, 2014 at 14:54 UTC
The following one-liner neatly illustrates why `length` is faster on strings than numbers... `perl -MDevel::Peek -e'Dump($_) for "42", 42'` [download] `use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name`	[reply] [d/l] [select]
Re^2: length() and the Schwartzian transform by hazylife (Monk) on Feb 27, 2014 at 13:46 UTC
Wow you're quick. Thanks for the benchmark. I guess 'num-sort' is not that much faster than 'num-ST' because in both cases there's still one (but only one!) round of stringification being performed per sub call (explicit pre-stringification in num-ST and implicit, sort of in-place stringification in num-sort).	[reply]


Do you know where your variables are?
	PerlMonks