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

[Bennett Todd <bet@newritz.mordor.net>]

1999-08-05-17:15:03 Amir Karger:
> > 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.
>[...]
> 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.

Ayup. Although the optimal algorithm will be faster, I agree 100% that the
difference won't make a difference until you get into things like Monte Carlo
simulations. And the schwartzian version has the big edge that at least for
those of us comfortable with the schwartzian transform, it's way easier to get
right --- either it's completely dead or it's perfectly correct --- whereas
there are any number of off-by-one fencepost type errors that you can trip
over in Fisher-Yates that will give you obscure, hard-to-notice failures to
perfectly shuffle the deck.

But the maximally-dense Fisher-Yates has the fun characteristic that it's
beautifully free of any hint of internal documentation as to what the heck
it's doing; it's almost nothing but punctuation marks. Writing code like
that as fast as I can type, KB after KB of it, scratches an itch I get after
reading too many posts by one particularly vocal contributer to p5p. I can
sit and fantasize that if I do it long enough, he'll eventually get questions
from people trying to figure out my code and begging for help, or better
still questions from people trying to cut-n-paste something from my code and
failing.

Oh and P.S. I think I actually did have an off-by-one in my version, though I
think it just just made it waste an unnecessary extra time around, didn't hurt
the shuffle. Fixed here; init $i to $#_ rather than @_.

-Bennett

	for(my$i=$#_;$i>0;$i--){@_[$_,$i]=@_[$i,$_]for rand$i+1}

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