G'day misterperl,
Other than a number of solutions involving modules, there were several pure Perl solutions.
I was interested in how these might compare.
The results I got were unexpected; I added a lot of variations (currently up to 14) but the same trend continued.
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.
Given these extractions might have been done multiple times for the same data,
I suspect Perl (v5.34.0) is performing some optimisation and perhaps caching results;
I would be interested in results others receive using different Perl versions.
In case there's concern about the number of tests, the entire benchmark should run in under a minute:
a COUNT of zero indicates 3 seconds for each of the 14 tests, plus a few seconds for other overhead.
Here's a rough breakdown of the results:
-
Schwartzian Transform: slowest.
Test names begin with ST.
-
Guttman-Rosler Transform: second slowest but roughly twice as fast as Schwartzian Transform.
Test names begin with GRT.
-
syphilis' solution: about 40-50% faster than Guttman-Rosler Transform;
removing the length calculation added a small boost.
Test names begin with mcs.
-
Other solutions only using sort were the hands-down winners by far.
Their speeds varied slightly between runs; the results were too close to call.
Test names begin with s.
Here's a sample run.
It might be worth using the "download" link to see this without wrapping.
Perl & OS:
v5.34.0 on cygwin
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 STraen STran STra STrn STren STr GRTp
+e GRTpeq mcsl mcs sp sr ss sra
STraen 68.2/s -- -0% -1% -2% -3% -5% -54
+% -54% -60% -61% -100% -100% -100% -100%
STran 68.6/s 0% -- -0% -1% -3% -4% -54
+% -54% -60% -61% -100% -100% -100% -100%
STra 68.6/s 1% 0% -- -1% -2% -4% -53
+% -54% -60% -61% -100% -100% -100% -100%
STrn 69.3/s 2% 1% 1% -- -1% -3% -53
+% -54% -59% -60% -100% -100% -100% -100%
STren 70.4/s 3% 3% 3% 2% -- -2% -52
+% -53% -59% -60% -100% -100% -100% -100%
STr 71.5/s 5% 4% 4% 3% 2% -- -52
+% -52% -58% -59% -100% -100% -100% -100%
GRTpe 147/s 116% 115% 115% 113% 109% 106% -
+- -1% -13% -16% -100% -100% -100% -100%
GRTpeq 149/s 119% 118% 118% 116% 112% 109% 1
+% -- -12% -15% -100% -100% -100% -100%
mcsl 170/s 149% 148% 148% 145% 141% 138% 15
+% 14% -- -3% -100% -100% -100% -100%
mcs 175/s 157% 156% 155% 153% 149% 145% 19
+% 17% 3% -- -100% -100% -100% -100%
sp 263168/s 385629% 383801% 383272% 379410% 373718% 368096% 178350
+% 175994% 154699% 149996% -- -2% -2% -3%
sr 268680/s 393708% 391841% 391301% 387358% 381547% 375807% 182088
+% 179682% 157941% 153139% 2% -- -0% -1%
ss 269453/s 394842% 392970% 392428% 388474% 382646% 376890% 182612
+% 180200% 158396% 153581% 2% 0% -- -0%
sra 270688/s 396651% 394771% 394227% 390254% 384400% 378617% 183450
+% 181026% 159122% 154285% 3% 1% 0% --
There was a typo in the code; see update below.
The original Benchmarks: section is in the spoiler below.
Benchmarks:
Note: Unordered data extended with 'map "a-$_", shuffle 0..10000'
Rate STra STr STrn STran STraen STren GRTpe
+q GRTpe mcsl mcs sra sp sr ss
STra 69.0/s -- -0% -0% -1% -1% -2% -52
+% -52% -58% -60% -100% -100% -100% -100%
STr 69.3/s 0% -- -0% -1% -1% -1% -52
+% -52% -58% -60% -100% -100% -100% -100%
STrn 69.3/s 0% 0% -- -1% -1% -1% -51
+% -52% -58% -60% -100% -100% -100% -100%
STran 69.7/s 1% 1% 1% -- -0% -1% -51
+% -51% -58% -60% -100% -100% -100% -100%
STraen 69.7/s 1% 1% 1% 0% -- -0% -51
+% -51% -58% -60% -100% -100% -100% -100%
STren 70.1/s 2% 1% 1% 1% 0% -- -51
+% -51% -58% -59% -100% -100% -100% -100%
GRTpeq 143/s 107% 106% 106% 105% 105% 104% -
+- -0% -14% -17% -100% -100% -100% -100%
GRTpe 144/s 108% 107% 107% 106% 106% 105% 0
+% -- -14% -17% -100% -100% -100% -100%
mcsl 166/s 141% 140% 140% 138% 138% 137% 16
+% 16% -- -4% -100% -100% -100% -100%
mcs 173/s 150% 149% 149% 148% 148% 146% 21
+% 20% 4% -- -100% -100% -100% -100%
sra 269609/s 390588% 389108% 388890% 386666% 386573% 384706% 188564
+% 187751% 162119% 156078% -- -1% -1% -1%
sp 271738/s 393672% 392181% 391961% 389720% 389626% 387744% 190053
+% 189234% 163400% 157311% 1% -- -1% -1%
sr 273197/s 395787% 394288% 394067% 391813% 391719% 389826% 191074
+% 190251% 164278% 158157% 1% 1% -- -0%
ss 273197/s 395787% 394288% 394067% 391813% 391719% 389826% 191074
+% 190251% 164278% 158157% 1% 1% 0% --
Here's the code:
#!/usr/bin/env perl
use strict;
use warnings;
use namespace::autoclean;
use Benchmark 'cmpthese';
use List::Util 'shuffle';
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
push @unordered, map "a-$_", shuffle 0..10000;
print "Benchmarks:\n";
print " Note: Unordered data extended with 'map \"a-\$_\", shuffle
+0..10000'\n";
my $count = 0;
cmpthese $count => \%coderef_for;
sub sort_regex {
sort {
($a =~ /(\d+)/)[0] <=> ($b =~ /(\d+)/)[0]
} @unordered;
}
sub st_regex {
map {
$_->[0]
}
sort {
$a->[1] <=> $b->[1]
}
map {
[$_, (/(\d+)/)[0]]
} @unordered;
}
sub st_regex_no_index {
map {
$_->[0]
}
sort {
$a->[1] <=> $b->[1]
}
map {
[$_, /(\d+)/]
} @unordered;
}
sub st_regex_expr_ni {
map $_->[0],
sort {
$a->[1] <=> $b->[1]
}
map [$_, /(\d+)/], @unordered;
}
sub sort_regex_anchored {
sort {
($a =~ /(\d+)$/)[0] <=> ($b =~ /(\d+)$/)[0]
} @unordered;
}
sub st_regex_anchored {
map {
$_->[0]
}
sort {
$a->[1] <=> $b->[1]
}
map {
[$_, (/(\d+)$/)[0]]
} @unordered;
}
sub st_regex_anch_ni {
map {
$_->[0]
}
sort {
$a->[1] <=> $b->[1]
}
map {
[$_, /(\d+)$/]
} @unordered;
}
sub st_regex_anch_expr_ni {
map $_->[0],
sort {
$a->[1] <=> $b->[1]
}
map [$_, /(\d+)$/], @unordered;
}
sub sort_substr {
sort {
substr($a, 2) <=> substr($b, 2)
} @unordered;
}
sub map_cat_substr {
map {
'a-' . $_
}
sort {
$a <=> $b
}
map {
substr $_, 2
} @unordered;
}
sub map_cat_substr_len {
map {
'a-' . $_
}
sort {
$a <=> $b
}
map {
substr $_, 2, length($_) - 2
} @unordered;
}
sub sort_pack {
sort {
pack(L => substr($a, 2)) cmp pack(L => substr($b, 2))
} @unordered;
}
sub grt_pack_expr {
map substr($_, 4),
sort
map pack(L => substr($_, 2)) . $_, @unordered;
}
sub grt_pack_expr_q {
map substr($_, 8),
sort
map pack(Q => substr($_, 2)) . $_, @unordered;
}
Notes on pack:
-
I'm not any great expert with this function.
Happy to receive corrections, advice, etc.
-
The doco indicates that the "Q" template is not universally available.
If you don't have it, you might want to remove &grt_pack_expr_q
and the two lines referencing it in %expanded_abbrev_for and %coderef_for
(the key is "GRTpeq" in both cases).
If you do have it, be aware others, with whom you share your code, might not.
Update:
There was a typo in my original code: the first key/value pair in %coderef_for
was sr => \&sort_substr but it should have been sr => \&sort_regex.
I've fixed my code locally and edited the code above to reflect this fix.
I reran the code and have posted a new Benchmarks: section.
All of the output before Benchmarks: is unchanged from the original posting.
The old Benchmarks: section is now in a spoiler.
The results are not particularly different
— except sr and ss are no longer identical; although, still too close to call —
and my original "rough breakdown of the results" has not changed.
|