Re^2: About List::Util's pure Perl shuffle()

Adding your optimization to BrowerUK's version, we get the best yet.

sub ikegami (@) {
    my @a=@_;
    my $i=@a;
    my $n;
    my $x;
    map +( $n=rand($i--), $x=$a[$n], $a[$n]=$a[$i] )[1], @a
}
[download]

           Rate    naive listutil   runrig broweruk  ikegami
naive     636/s       --      -6%     -19%     -26%     -37%
listutil  675/s       6%       --     -14%     -21%     -33%
runrig    785/s      23%      16%       --      -9%     -22%
broweruk  859/s      35%      27%       9%       --     -15%
ikegami  1010/s      59%      50%      29%      18%       --
[download]

Of course, this doesn't always help. For example, try shuffling somewhat long strings.

our @data = map { 'x' x 1000 } 1..1000;
cmpthese -3, { map { $_ => "$_ \@data" } qw/naive listutil broweruk ru
+nrig ikegami/ };
[download]

          Rate   runrig    naive  ikegami listutil broweruk
runrig   118/s       --     -10%     -40%     -43%     -86%
naive    131/s      11%       --     -34%     -37%     -85%
ikegami  197/s      68%      51%       --      -5%     -77%
listutil 207/s      76%      58%       5%       --     -76%
broweruk 860/s     632%     558%     336%     315%       --
[download]

Update: runrig pointed out that my shuffle was broken. I changed $a[$n] to $x=$a[$n] to fix it. It slowed down my solution, but not by much.

Comment on Re^2: About List::Util's pure Perl shuffle() Select or Download Code

Replies are listed 'Best First'.
Re^3: About List::Util's pure Perl shuffle() by blazar (Canon) on Jul 12, 2007 at 09:58 UTC
Update: runrig pointed out that my shuffle was broken. I changed `$a[$n]` to `$x=$a[$n]` to fix it. It slowed down my solution, but not by much. Ok, that's the same trick as BrowserUk's, except that in that form it's even more elegant. Anyway... c'mon! I'm not ashamed the very least to ask why does it work. I can't understand...	[reply] [d/l] [select]
Re^4: About List::Util's pure Perl shuffle() by ikegami (Patriarch) on Jul 12, 2007 at 13:29 UTC
It's similar to `print($i, $i++, $i);`, at least in effect. Perl must place some form of pointer* to `$a[$n]`'s value on a stack instead of making a new scalar to save speed and memory. The result is that when `$a[$n]` is changed by the third expression in the list slice, it also changes the value of the second expression. By explicitly copying the value of `$a[$n]` into another variable (`$x`), changes in `$a[$n]` no longer affect the result of the slice. * — An alias? A pointer to the SV?	[reply] [d/l] [select]


Do you know where your variables are?
	PerlMonks