Beefy Boxes and Bandwidth Generously Provided by pair Networks Ovid
Do you know where your variables are?
 
PerlMonks  

${Schwartzian transform} ?

by liz (Monsignor)
on Sep 18, 2003 at 11:53 UTC ( #292363=perlmeditation: print w/ replies, xml ) 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

Comment on ${Schwartzian transform} ?
Download Code
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 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 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.

    Already an object
    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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://292363]
Approved by ybiC
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (7)
As of 2014-04-20 19:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (487 votes), past polls