in reply to Re: How can I do a numeric sort on a substring? [Benchmark]
in thread How can I do a numeric sort on a substring?

> I had thought that the Schwartzian and Guttman-Rosler transformations would have been the fastest, but that wasn't the case. In fact, those that performed extraction of the number, prior to comparison, within the sort, were the quickest

you are only testing with 10 elements in your @unordered array.

for n elements you have in best case O(n*log(n)) comparisons but O(n) packs and unpacks with ST and GRT, which means the overhead to extract n numbers will account much more for small n.

use at least n >> 1000 elements for a real benchmark.

Rule of thumb : the choice of algorithm is almost always neglectable for small data.

update

it's like getting the Porsche out of the garage to buy a six-pack of beer just 10m around the corner.

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Replies are listed 'Best First'.
Re^3: How can I do a numeric sort on a substring? [Benchmark]
by kcott (Archbishop) on Jun 27, 2021 at 02:41 UTC

    G'day Rolf,

    "you are only testing with 10 elements in your @unordered array."

    The code only contains one comment which I added for the express purpose of heading off such feedback: 

    # Extend @unordered for improved benchmarking
push @unordered, map "a-$_", shuffle 0..10000;

    [download]
    "use at least n >> 1000 elements for a real benchmark"

    Indeed. I used 10,011 elements "for improved benchmarking".

    The preamble tests were to check that all subroutines returned identical results. Each of the preamble tests were only run once and did not involve any benchmarking; they were intended as a sanity check (processing stopped here if --dry_run was used). The data used for this had 10 elements, which I considered sufficient for these tests, and was indicated by: 

    Unordered data (for preamble tests):

    [download]

    — Ken

[reply]
[d/l]
[select]
      Hi Ken

      > I added for the express purpose of heading off such feedback

      Oops, sorry I missed that. :/

      I can't dig deeper now, but some suggestions, to solve the miracle

      • it's still logarithmic, maybe try 1e6 elements instead
      • Perl is propagating the caller's context to the returning statement, maybe you should check if benchmark is using list context too?

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery

[reply]
        > Perl is propagating the caller's context to the returning statement, maybe you should check if benchmark is using list context too?

        my suspicion was justified, the benchmarks are in void context, that's why simple sorts are just doing nothing. ( and nothing is fast ;)

        I took your code and forced all subs to operate in list context, by prepending @ordered = in the first line.

        That's the result with 10000 elements (you can also adjust $max for more or less elements)

        Perl & OS:
    v5.32.1 on MSWin32
Unordered data (for preamble tests):
    a-10 a-01 a-22 a-2 a-0 a-3 a-000 a-1 a-12345 a-1
Preamble tests:
    grt_pack_expr:         a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    grt_pack_expr_q:       a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    st_regex:              a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    st_regex_anchored:     a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    st_regex_anch_expr_ni: a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    st_regex_anch_ni:      a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    st_regex_expr_ni:      a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    st_regex_no_index:     a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    map_cat_substr:        a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    map_cat_substr_len:    a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    sort_pack:             a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    sort_regex:            a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    sort_regex_anchored:   a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
    sort_substr:           a-0 a-000 a-01 a-1 a-1 a-2 a-3 a-10 a-22 a-
+12345
Legend:
    GRTpe:  grt_pack_expr
    GRTpeq: grt_pack_expr_q
    STr:    st_regex
    STra:   st_regex_anchored
    STraen: st_regex_anch_expr_ni
    STran:  st_regex_anch_ni
    STren:  st_regex_expr_ni
    STrn:   st_regex_no_index
    mcs:    map_cat_substr
    mcsl:   map_cat_substr_len
    sp:     sort_pack
    sr:     sort_regex
    sra:    sort_regex_anchored
    ss:     sort_substr
Benchmarks:
    Note: Unordered data extended with 'map "a-$_", shuffle 0..10000'
         Rate   sra    sr   sp STra  STr STren STraen STran STrn   ss 
+ mcs mcsl GRTpeq GRTpe
sra    3.34/s    --   -2% -73% -81% -82%  -82%   -82%  -82% -82% -85% 
+-92% -92%   -93%  -95%
sr     3.40/s    2%    -- -72% -80% -81%  -82%   -82%  -82% -82% -85% 
+-92% -92%   -92%  -95%
sp     12.3/s  270%  263%   -- -28% -32%  -34%   -34%  -35% -35% -44% 
+-71% -72%   -72%  -82%
STra   17.2/s  416%  406%  39%   --  -5%   -8%    -8%   -9% -10% -22% 
+-59% -60%   -61%  -75%
STr    18.2/s  445%  435%  47%   6%   --   -2%    -3%   -4%  -4% -18% 
+-57% -58%   -59%  -73%
STren  18.6/s  459%  448%  51%   8%   2%    --    -0%   -1%  -2% -16% 
+-56% -57%   -58%  -73%
STraen 18.7/s  461%  451%  52%   9%   3%    0%     --   -1%  -2% -16% 
+-55% -57%   -58%  -72%
STran  18.9/s  467%  456%  53%  10%   4%    1%     1%    --  -1% -15% 
+-55% -56%   -58%  -72%
STrn   19.0/s  471%  460%  54%  11%   5%    2%     2%    1%   -- -14% 
+-55% -56%   -57%  -72%
ss     22.2/s  565%  552%  80%  29%  22%   19%    18%   17%  16%   -- 
+-47% -49%   -50%  -67%
mcs    42.0/s 1159% 1136% 240% 144% 131%  125%   124%  122% 121%  89% 
+  --  -3%    -6%  -38%
mcsl   43.3/s 1199% 1174% 251% 152% 138%  132%   131%  129% 128%  95% 
+  3%   --    -3%  -36%
GRTpeq 44.7/s 1239% 1214% 262% 160% 146%  140%   138%  136% 135% 101% 
+  6%   3%     --  -34%
GRTpe  67.9/s 1937% 1898% 451% 295% 273%  264%   263%  259% 257% 206% 
+ 62%  57%    52%    --

        [download]

        here the code

        #!/usr/bin/env perl

use strict;
use warnings;
use namespace::autoclean;

use Benchmark 'cmpthese';
use List::Util 'shuffle';

my @ordered;
my @unordered = qw{a-10 a-01 a-22 a-2 a-0 a-3 a-000 a-1 a-12345 a-1};
my %expanded_abbrev_for = (
    sr => 'sort_regex',
    STr => 'st_regex',
    STrn => 'st_regex_no_index',
    STren => 'st_regex_expr_ni',
    sra => 'sort_regex_anchored',
    STra => 'st_regex_anchored',
    STran => 'st_regex_anch_ni',
    STraen => 'st_regex_anch_expr_ni',
    ss => 'sort_substr',
    mcs => 'map_cat_substr',
    mcsl => 'map_cat_substr_len',
    sp => 'sort_pack',
    GRTpe => 'grt_pack_expr',
    GRTpeq => 'grt_pack_expr_q',
);
my %coderef_for = (
    sr => \&sort_regex,
    STr => \&st_regex,
    STrn => \&st_regex_no_index,
    STren => \&st_regex_expr_ni,
    sra => \&sort_regex_anchored,
    STra => \&st_regex_anchored,
    STran => \&st_regex_anch_ni,
    STraen => \&st_regex_anch_expr_ni,
    ss => \&sort_substr,
    mcs => \&map_cat_substr,
    mcsl => \&map_cat_substr_len,
    sp => \&sort_pack,
    GRTpe => \&grt_pack_expr,
    GRTpeq => \&grt_pack_expr_q,
);

print "Perl & OS:\n    $^V on $^O\n";
print "Unordered data (for preamble tests):\n    @unordered\n";
print "Preamble tests:\n";
my $tests_fmt = "    %-22s %s\n";

for my $name (sort keys %coderef_for) {
    printf $tests_fmt, "$expanded_abbrev_for{$name}:",
            "@{[$coderef_for{$name}->()]}";
}

exit if @ARGV && $ARGV[0] eq '--dry_run';

print "Legend:\n";
my $legend_fmt = "    %-7s %s\n";

for my $abbrev (sort keys %expanded_abbrev_for) {
    printf $legend_fmt, "$abbrev:",
            $expanded_abbrev_for{$abbrev};
}

# Extend @unordered for improved benchmarking
my $max = 10000;
push @unordered, map "a-$_", shuffle 0..$max;

print "Benchmarks:\n";
print "    Note: Unordered data extended with 'map \"a-\$_\", shuffle 
+0..$max'\n";
my $count = 0;
cmpthese $count => \%coderef_for;

sub sort_regex {
    @ordered =
    sort {
        ($a =~ /(\d+)/)[0] <=> ($b =~ /(\d+)/)[0]
    } @unordered;
}

sub st_regex {
    @ordered =
    map {
        $_->[0]
    }
    sort {
        $a->[1] <=> $b->[1]
    }
    map {
        [$_, (/(\d+)/)[0]]
    } @unordered;
}

sub st_regex_no_index {
    @ordered =
    map {
        $_->[0]
    }
    sort {
        $a->[1] <=> $b->[1]
    }
    map {
        [$_, /(\d+)/]
    } @unordered;
}

sub st_regex_expr_ni {
    @ordered =
    map $_->[0],
    sort {
        $a->[1] <=> $b->[1]
    }
    map [$_, /(\d+)/], @unordered;
}

sub sort_regex_anchored {
    @ordered =
    sort {
        ($a =~ /(\d+)$/)[0] <=> ($b =~ /(\d+)$/)[0]
    } @unordered;
}

sub st_regex_anchored {
    @ordered =
    map {
        $_->[0]
    }
    sort {
        $a->[1] <=> $b->[1]
    }
    map {
        [$_, (/(\d+)$/)[0]]
    } @unordered;
}

sub st_regex_anch_ni {
    @ordered =
    map {
        $_->[0]
    }
    sort {
        $a->[1] <=> $b->[1]
    }
    map {
        [$_, /(\d+)$/]
    } @unordered;
}

sub st_regex_anch_expr_ni {
    @ordered =
    map $_->[0],
    sort {
        $a->[1] <=> $b->[1]
    }
    map [$_, /(\d+)$/], @unordered;
}

sub sort_substr {
    @ordered =
    sort {
        substr($a, 2) <=> substr($b, 2)
    } @unordered;
}

sub map_cat_substr {
    @ordered =
    map {
        'a-' . $_
    }
    sort {
        $a <=> $b
    }
    map {
        substr $_, 2
    } @unordered;
}

sub map_cat_substr_len {
    @ordered =
    map {
        'a-' . $_
    }
    sort {
        $a <=> $b
    }
    map {
        substr $_, 2, length($_) - 2
    } @unordered;
}

sub sort_pack {
    @ordered =
    sort {
        pack(L => substr($a, 2)) cmp pack(L => substr($b, 2))
    } @unordered;
}

sub grt_pack_expr {
    @ordered =
    map substr($_, 4),
    sort
    map pack(L => substr($_, 2)) . $_, @unordered;
}

sub grt_pack_expr_q {
    @ordered =
    map substr($_, 8),
    sort
    map pack(Q => substr($_, 2)) . $_, @unordered;
}

        [download]

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom