http://www.perlmonks.org?node_id=441099


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.

Replies are listed 'Best First'.
Re^3: A bad shuffle
by jdporter (Paladin) 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.)

[reply]
[d/l]

      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];
  } @_;
}

      [download]
      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%    --

      [download]

      the lowliest monk

[reply]
[d/l]
[select]

In Section Meditations