On Wed, Apr 03, 2002 at 10:37:08PM -0700, Sean M. Burke wrote:
> I was looking at the implementation of the FY shuffle that I see in
> Perlfaq4, namely:
>
> sub fy1 {
> my $deck = shift; # $deck is a reference to an array
> my $i = @$deck;
> while (--$i) {
> my $j = int rand ($i+1);
> @$deck[$i,$j] = @$deck[$j,$i];
> }
> }
>
> And I thought "guh, that looks a bit off" -- notably, it dies when given an
> empty array.
Yeah. It's odd. FY is a simple algorithm, which can be copied from many
sources, and yet people seem to be able to screw it up all the time.
The one in Algorithm::Numeric::Shuffle, of which the FAQ entry was
derived, doesn't have a problem with empty arrays though.
I must say however, that requiring that the array is passed as a
reference seems an oddity to me. If you pass it a list, it should,
IMO, return the shuffled list.
> So I banged out the following, which I'm pretty sure does the same work:
>
> sub fy2 {
> my($deck,$i,$j,$t) = $_[0];
> $i = @$deck || return;
> while(1) {
> $j = int rand($i-- || return);
> $t = $deck->[$i];
> $deck->[$i] = $deck->[$j];
> $deck->[$j] = $t;
> }
> }
> # Thanks to Silmaril for pointing out that the temp var is faster
But this one is butt ugly! '|| return' inside a call to rand() is nice
for obfuscation purposes, it doesn't make readable programs. Nor does
it make for a solution that's easily converted to one that shuffles a
given list. Therefore, I think such trickery doesn't belong in the FAQ.
I'd prefer to just fix the error in fy1, and put
sub fy1 {
my $deck = shift; # $deck is a reference to an array
my $i = @$deck;
while ($i--) {
my $j = int rand ($i+1);
@$deck[$i,$j] = @$deck[$j,$i];
}
}
in the FAQ. Speed isn't holy - if you want speed, you would have used
Inline::C or XS anyway.
Besides, it would be better to fix perl such that both cases are
equivalent. ;-)
> And besides fixing the bug with empty arrays, it runs twenty-odd percent
> faster.
> That ratio seems to hold true whether the deck is numbers, strings, or objects
That's not very surprising, because the values of the elements
aren't accessed at all.
> I was quite surprised -- it seems too good to be true. Am I doing anything
> obviously wrong?
Can't spot any problems.
Abigail
