Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
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 pondering the Monastery: (14)
As of 2014-10-01 12:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (10 votes), past polls