Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re^2: A bad shuffle

by Anonymous Monk
on Mar 21, 2005 at 01:43 UTC ( #441099=note: print w/ replies, xml ) Need Help??


in reply to Re: A bad shuffle
in thread A bad shuffle

Actually, the original "naive_shuffle" is not a Fisher-Yates shuffle, it is a "naive shuffle" implementation. The OP's analysis is correct.

His final algorithm, however, is a correct Fisher-Yates implementation.


Comment on Re^2: A bad shuffle
Re^3: A bad shuffle
by jdporter (Canon) on Mar 21, 2005 at 03:29 UTC

    perlfaq4: How do I shuffle an array randomly? not only gives a "canonical" implementation of the Fisher-Yates algorithm in Perl, but also refers to the List::Util module's shuffle function, which is an implementation of Fisher-Yates in C. The algorithm is also implemented in Abigail's Algorithm::Numerical::Shuffle, the doco of which gives some citations into the literature (Knuth, Fisher&Yates, etc.).

    The Fisher-Yates has also been discussed many times on clpm. (You can do a Google Groups search. My ego compels me to link to this posting by yrs trly, which isn't about F-Y, but uses it.)

      Yes, I was looking at the code for List::Util earlier today. In addition to the C implementatin of the Fisher-Yates shuffle, it includes the following "backup" in Perl:

      sub shuffle (@) { my @a=\(@_); my $n; my $i=@_; map { $n = rand($i--); (${$a[$n]}, $a[$n] = $a[$i])[0]; } @_; }
      Pretty gnarleous, IMO. Kind of like a hybrid between F-Y and Tanktalus's shuffler.

      The C implementation of List::Util::shuffle is 10-20x faster than the Perl implementation. For the practical programmer: end of story. Still, to satisfy my monkly preoccupation with how many angels can lambada on the head of a pin, and more importantly, in order to reduce this dead horse to a thin protein film, I benchmarked the three shufflers: ta = Tanktalus's shuffler; lu = Perl implementation of List::Util::shuffle; rp = random_perm:

      N = 1000 Rate rp lu ta rp 230/s -- -10% -22% lu 257/s 12% -- -13% ta 296/s 29% 15% -- N = 10_000 Rate ta lu rp ta 14.3/s -- -27% -34% lu 19.6/s 37% -- -10% rp 21.7/s 52% 11% -- N = 100_000 Rate ta lu rp ta 0.144/s -- -92% -93% lu 1.75/s 1118% -- -13% rp 2.01/s 1302% 15% --

      the lowliest monk

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (8)
As of 2015-07-06 22:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (84 votes), past polls