I recently worked on a small project simulating random events that were far too numerous to enumerate. In such cases, every bit of speed matters.
The project in this case was similar to determining likelihood of five-card Poker hands in seven-card draws.
Simulation of shuffling the deck and drawing cards can take a large part of the runtime if not done well, but there's a trick that makes it almost trivial.
The deck itself is represented as an array of cards. It doesn't matter whether the cards are represented by integers, objects, or anything else, as long as the entry in the array itself is short. A pointer to a struct (in C-like languages) or a reference to an object (in most languages) would work very well.
The fair shuffling algorithm divides the deck into shuffled and unshuffled parts. In the middle of the shuffle, it might look like this, with "S" being a shuffled card and "U" unshuffled:
At each step, one of the unshuffled cards is selected uniformly randomly, and swapped with the card in the leading unshuffled spot (which may by chance be the same spot). That leading spot is then considered to be shuffled.
The algorithm starts by considering all positions to be unshuffled, and proceeds to the last position.
This algorithm produces a perfectly fair shuffle, with each card having equal probability of appearing in any spot, and each permutation having an equal chance of occurring.
After shuffling, the hand is "drawn" from the front of the deck by taking the first 7 cards. An array of these cards is then passed to whatever functions need to know the hand.
The trick is to recognize three things:
- Only the first 7 cards of the deck need to be shuffled, not all 52;
- If the functions are coded to support it, the array of the deck can be passed as the array of the hand; and,
- Because the shuffle is perfectly fair, the partially-shuffled deck can be reused in the next iteration as-is.
This means that the shuffle-and-draw loop would look something like this:
def simulate(rounds): global CARDS # Array of 52 cards for j in range(rounds): for i in range(7): x = rand(52 - i) + i CARDS[i], CARDS[x] = CARDS[x], CARDS[i] analyze(CARDS)
This has the following runtime properties:
- Shuffle-and-draw requires only 7 randoms and 7 memory swaps.
- Indirection is minimized, which is needed if
analyzemust access array elements multiple times each call.
- No memory is copied or allocated.
As a result, it's a blazing-fast way to generate random hands.
The author does not allow comments to this entry