Re: [FWP] Shuffling (was Re: [FWP] Perl Card Games)

[Amir Karger <karger@fermi2.chem.yale.edu>]

On Thu, Aug 05, 1999 at 04:16:52PM +0000, Bennett Todd wrote:
> So Fisher-Yates looks like
> 
> 	for (my $i = @_; $i > 0; $i--) {
> 		@_[$i, $_] = @_[$_, $i] for rand $i+1;
> 	}

Is this use of "for" as a simple statement documented? Also, I'm not sure it
works for me.

> As far as I can see, though, your schwartzian shuffle and Fischer-Yates
> should both be perfectly random 

woo-hoo!

> I suspect yours has a potential for a wee teensy theoretical bias; if you
> rand should happen to croak out two identical floats within the run

Identical floats? This is a real concern since I had planned on setting my
linux box to shuffle the deck with maximum priority with nothing else on the
system until the sun goes out ("Oh, five *billion* years? Phew! I thought you
said five *million*.")

> the other hand I'd always mis-implemented Fisher-Yates, when I coded it
> with swaps, so it forced every card in the deck to move into a different
> spot, rather than giving it its one-in-N chance of remaining unmoved. A
> substantially worse error.

But I kind of suspect that the effect this has on, say, a card game, would
be really difficult to notice; it's not like it would tend to give a
specific player an advantage, and even so, the naive shuffle is only
non-random by a small amount, which is probably less than random noise as
long as you play fewer than 10^6 games in your life.

> Mostly, though, your shuffle just makes the machine work a bit harder; doing
> N-1 rands and swaps is appreciably cheaper than doing N rands and an
> O[n log n] sort.

Hm. Well, that's probably true, but remember that we never plan to shuffle
more than 52 cards. And few card games require you to, say, shuffle the
deck a hundred thousand times between each player's turn. I did a benchmark
to check. I've never benchmarked before, but I think I did it right. I
got the following times for 10000 iterations of shuffling a 52-member array:

Fisher-Yates:  5 secs
Naive (bad):  9 secs
Schwartzian: 12 secs

Incidentally, with 1000 iterations of a list of 500, I get 5, 8, and 17
seconds.  And for those of you trying to graph N vs. N log N on your
calculators, I did 100 iterations of a list of 5000, and got 5, 8, and 24
seconds.

Luckily we don't have decks with 5000 cards, or we would have to worry about
the .24-second lag time between games.

My conclusion is that for small sets, the Schwartzian is a fun way to do it,
but of course we should all use the Fisher-Yates method for large sets
(where both time and memory overheads could become an issue), or
for applications that matter.

-Amir

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe