Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

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

by ikegami (Pope)
on Jul 11, 2007 at 17:47 UTC ( #626057=note: print w/ replies, xml ) Need Help??


in reply to Re: About List::Util's pure Perl shuffle()
in thread 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 }
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% --

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/ };
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% --

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
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...

      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?

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://626057]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (9)
As of 2014-12-21 12:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (105 votes), past polls