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
|