Re^2: quick sort. How do it faster

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.

Comment on Re^2: quick sort. How do it faster Download Code

Replies are listed 'Best First'.
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]