P is for Practical PerlMonks

### \${Schwartzian transform} ?

by liz (Monsignor)
 on Sep 18, 2003 at 11:53 UTC Need Help??

Sometimes I wonder why the Schwartzian Transform isn't written as:
```my @output =
map { \${\$_->[0]} }
sort { \$a->[1] cmp \$b->[1] }
map { [\\$_, expensive_func(\$_)] }
@input;
to avoid copying the original values around?

Liz

Replies are listed 'Best First'.
Re: \${Schwartzian transform} ?
by Abigail-II (Bishop) on Sep 18, 2003 at 12:07 UTC
Perhaps because it's not clear how much a win this will be? Copying a scalar requires making a new scalar. Making a ref also requires making a new scalar. There might be a small win, but it's probably dwarved by the expensive_func call. The following benchmark shows that the gain is small:
```#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw /cmpthese/;

our @array = map {sprintf "aaa:%03d" => \$_} 0 .. 999;
our (@a, @b);

for (my \$i = @array; -- \$i;) {
my \$j = rand (\$i + 1);
@array [\$i, \$j] = @array [\$j, \$i];
}

cmpthese -5 => {
ST  => '@::a = map  {\$_ -> [0]}
sort {\$a -> [1] <=> \$b -> [1]}
map  {[\$_ => substr \$_, 4]} @array',
Liz => '@::b = map  {\${\$_ -> [0]}}
sort {\$a -> [1] <=> \$b -> [1]}
map  {[\\$_ => substr \$_, 4]} @array',
};

foreach my \$i (0 .. 999) {
die unless \$a [\$i] eq \$b [\$i];
}

__END__
Benchmark: running Liz, ST for at least 5 CPU seconds...
Liz:  5 wallclock secs ( 5.31 usr +  0.00 sys =  5.31 CPU) @ 10
+2.45/s (n=544)
ST:  5 wallclock secs ( 5.37 usr +  0.00 sys =  5.37 CPU) @ 10
+5.40/s (n=566)
Rate Liz  ST
Liz 102/s  -- -3%
ST  105/s  3%  --

Although you might know cases where there is a bigger gain.

Abigail

Instead of 3 a's, I've used 80 a's (more or less a normal line of text). On my iBook I get this:
```use strict;
use warnings;

use Benchmark qw /cmpthese/;

our @array = map {sprintf "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa:%03d" => \$_} 0 .. 999;
our (@a, @b);

for (my \$i = @array; -- \$i;) {
my \$j = rand (\$i + 1);
@array [\$i, \$j] = @array [\$j, \$i];
}

cmpthese -5 => {
ST  => '@::a = map  {\$_ -> [0]}
sort {\$a -> [1] <=> \$b -> [1]}
map  {[\$_ => substr \$_, 81]} @array',
Liz => '@::b = map  {\${\$_ -> [0]}}
sort {\$a -> [1] <=> \$b -> [1]}
map  {[\\$_ => substr \$_, 81]} @array',
};

foreach my \$i (0 .. 999) {
die unless \$a [\$i] eq \$b [\$i];
}
__END__
Rate   ST  Liz
ST  26.7/s   -- -10%
Liz 29.6/s  11%   --
which looks rather significant to me.

Your original benchmark doesn't show anything significant on my iBook, except that my approach is always faster but the difference is always less than .5%.

Liz

In general, 10% doesn't look significant to me for a Benchmark. It has been proven in the past that unless the difference is large, Benchmark results aren't well reproducable from platform to platform. Even changing the compiler with which perl was compiled (and leaving everything else the same), could change the order of the outcome of a Benchmark. For instance, if I run your version of the Benchmark, with a lead string of 80 a's, the original ST appears to be slightly *faster*:
```Benchmark: running Liz, ST for at least 5 CPU seconds...
Liz:  5 wallclock secs ( 5.28 usr +  0.01 sys =  5.29 CPU) @ 99
+.05/s (n=524)
ST:  5 wallclock secs ( 5.30 usr +  0.00 sys =  5.30 CPU) @ 10
+0.94/s (n=535)
Rate Liz  ST
Liz 99.1/s  -- -2%
ST   101/s  2%  --
Of course, if speed is a concern, you wouldn't use ST at all, you'd use GRT. Here's a benchmark with GRT included:
```#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw /cmpthese/;

our @array = map {("a" x 80) . sprintf ":%03d" => \$_} 0 .. 999;
our (@a, @b, @c);

for (my \$i = @array; -- \$i;) {
my \$j = rand (\$i + 1);
@array [\$i, \$j] = @array [\$j, \$i];
}

cmpthese -5 => {
ST  => '@::a = map  {\$_ -> [0]}
sort {\$a -> [1] <=> \$b -> [1]}
map  {[\$_ => substr \$_, 81]} @array',
Liz => '@::b = map  {\${\$_ -> [0]}}
sort {\$a -> [1] <=> \$b -> [1]}
map  {[\\$_ => substr \$_, 81]} @array',
GRT => '@::c = map  {substr (\$_, 4) . ":" . substr (\$_, 0, 3)}
sort
map  {substr (\$_, 81) . ":" . substr (\$_, 0, 80)} @
+array'
};

foreach my \$i (0 .. 999) {
die unless \$a [\$i] eq \$b [\$i] && \$a [\$i] eq \$c [\$i]
}

__END__

Benchmark: running GRT, Liz, ST for at least 5 CPU seconds...
GRT:  5 wallclock secs ( 5.33 usr +  0.00 sys =  5.33 CPU) @ 19
+8.87/s (n=1060)
Liz:  5 wallclock secs ( 5.31 usr +  0.00 sys =  5.31 CPU) @ 98
+.87/s (n=525)
ST:  6 wallclock secs ( 5.31 usr +  0.01 sys =  5.32 CPU) @ 10
+0.38/s (n=534)
Rate  Liz   ST  GRT
Liz 98.9/s   --  -2% -50%
ST   100/s   2%   -- -50%
GRT  199/s 101%  98%   --

Abigail

Re: \${Schwartzian transform} ?
by BrowserUk (Pope) on Sep 18, 2003 at 12:05 UTC

At a first glance, I think your creating extra work rather than saving any. \$_ is an alias, so when you include it in the anon. array, you are only passing a reference to the original value (ie. a scalar).

Your code is actually creating an extra reference to the scalar, (ie. copying the alias?), which it then has to dereference, hence doing slightly more work.

I *think*.

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
If I understand your problem, I can solve it! Of course, the same can be said for you.

While \$_ in a map is an alias, it doesn't mean that \$_ in rvalue context magically resolves to the alias instead of the value. Watch:
```perl -wle '@a = 1; @b = map {++ \$_ -> [0]} map {[\$_]} @a; print "@a";
+print "@b"'
1
2

No alias passes out of the right-most map.

Or a shorter example:

```perl -wle '@a = 1; @b = map {\$_} @a; \$a [0] ++; print "@a @b"'
2 1

@b isn't an array whose elements are aliases for the elements of @a.

Abigail

Re: \${Schwartzian transform} ?
by liz (Monsignor) on Sep 19, 2003 at 09:48 UTC
Contemplating it a little bit more myself the past days, I came up with the following reasons:
Simplicity
The way it's written by merlyn is simpler to understand. It is in fact pseudo-code, not real code.

The input may already consist of a reference or an object: no need to take a further reference in that case.

Alias / Copy On Write
Perl shouldn't have to copy the contents of \$_. You could consider it a bug that it does so now. I'm pretty sure this innefficiency won't exist in Perl 6.

Liz

Create A New User
Node Status?
node history
Node Type: perlmeditation [id://292363]
Approved by ybiC
Front-paged by broquaint
help
Chatterbox?
 Eily went to the wiktionary to check that the pronunciations of prawn and prone are actually similar. Turns out prawn can be an alternative form of porn... [Discipulus]: well i'm still at the end of the food chain.. [Discipulus]: so a new life as krill in prague will be good [erix]: wtf -- what's the idea, is this trolling, advertising, or what? [Discipulus]: but realisticly choroba your company would a hire a programmer as me?

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (8)
As of 2017-06-29 12:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (662 votes). Check out past polls.