Re: quick sort. How do it faster

With just a few syntax changes (no change to the logic) I can shave off about 8% of the run time...

sub sortQ2
{
    my ($s, $e, $dst) = @_;
    my $m = $s - 1;
    
    ($dst->[$_] < $dst->[$e]) && (
        ++$m,
        ($dst->[$m], $dst->[$_]) = ($dst->[$_], $dst->[$m]),
    ) for ($s .. $e-1);
    
    ++$m;
    
    ($dst->[$m], $dst->[$e]) = ($dst->[$e], $dst->[$m]);
    
    sortQ2($s, $m-1, $dst) if ($s < $m - 1);
    sortQ2($m+1, $e, $dst) if ($m + 1 < $e);
}
[download]

How does this speed things up? Each pair of { ... } introduces a lexical scope; scopes have a small runtime overhead. I've removed all of them except for the one surrounding the entire function.

You can get a few percent extra using Data::Alias which allows you to avoid some arrayref dereferencing operations:

use Data::Alias;

sub sortQ2
{
    my ($s, $e, $dst) = @_;
    alias my @dst = @$dst;
    my $m = $s - 1;
    
    ($dst[$_] < $dst[$e]) && (
        ++$m,
        ($dst[$m], $dst[$_]) = ($dst[$_], $dst[$m]),
    ) for ($s .. $e-1);
    
    ++$m;
    
    ($dst[$m], $dst[$e]) = ($dst[$e], $dst[$m]);
    
    ($s < $m - 1) && sortQ2($s, $m-1, $dst);
    ($m + 1 < $e) && sortQ2($m+1, $e, $dst);
}
[download]

Overall, this is about 12% faster than the original.

use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name

Comment on Re: quick sort. How do it faster Select or Download Code

Replies are listed 'Best First'.
Re^2: quick sort. How do it faster by BrowserUk (Patriarch) on Oct 20, 2013 at 11:08 UTC
See you and raise you to 34% :) `sub sortQ3{ local our @dst; ( my( $s, $e ), *dst ) = @_; my $t; my $m = $s-1; $dst[ $_ ] < $dst[ $e ] and $t = $dst[++$m], $dst[$m] = $dst[$_], $dst[$_] = $t for $s .. $e; $t = $dst[++$m], $dst[$m] = $dst[$e], $dst[$e] = $t; sortQ3( $s, $m-1, \@dst ) if $s < $m-1; sortQ3( $m+1, $e, \@dst ) if $m+1< $e; }` [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. .	[reply] [d/l]
Re^3: quick sort. How do it faster by tobyink (Canon) on Oct 23, 2013 at 13:50 UTC
Hmm... I'm surprised that introducing that temporary variable for swaps makes such a difference, but it does appear to. Do you have any explanation? Is it because it's saving a couple of array indexing operations, or is it just that `($x,$y)=($y,$x)` is implemented suboptimally by Perl? `use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name`	[reply] [d/l]
Re^4: quick sort. How do it faster by BrowserUk (Patriarch) on Oct 23, 2013 at 16:31 UTC
I'm surprised that introducing that temporary variable for swaps makes such a difference, but it does appear to. Do you have any explanation? Not really. Just that it seems to be some inefficiency inherent in the way list ops are implemented in perl. Perhaps even more surprising is that -- for numeric data -- the old saw, triple xor-assignment is more efficient than both the list assignment and the introduced temporary: `cmpthese -1,{ a=>q[ my( $a, $b ) = ( 1, 2 ); ( $a, $b ) = ( $b, $a ) for 1. +.1000; ], b=>q[ my( $a, $b,$t ) = ( 1, 2 ); $t = $a, $a = $b, $b = $t for 1. +.1000; ], c=>q[ my( $a, $b ) = ( 1, 2 ); $a ^= $b ^= $a ^= $b for 1. +.1000; ] };; Rate a b c a 3253/s -- -34% -42% b 4913/s 51% -- -13% c 5632/s 73% 15% --` [download] That really ought not be the case. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^4: quick sort. How do it faster by LanX (Saint) on Oct 24, 2013 at 12:41 UTC
> is implemented suboptimally by Perl? I doubt that list assignments can be implemented more efficiently w/o JIT magic. The behaviour of caching all values before assigning them is well defined, e.g. in Learning Perl ch. 3.4: Since the list is built up before the assignment starts, this makes it easy to swap two variables' values in Perl OTOH one could have tied vars on LHS which are not side effect free, such that compatibility would break after optimization to a ring-replacement. IMHO this can only be resolved at runtime .. (or with complicated precompiled case checks) Cheers Rolf ( addicted to the Perl Programming Language)	[reply]