Draw a Card from a Deck for a Monte Carlo Simulation of Poker

Question

At the moment I am working on an iOS-application in which I need to draw random cards from a carddeck. At the moment my Code looks like this:

- (PlayingCard*) drawRandomCard
{
    PlayingCard * randomCard = nil;

    NSUInteger index = arc4random_uniform(self.cards.count);
    randomCard = self.cards[index]; //self.cards is an NSArray of PlayingCard's
    while (randomCard.isUsed) {
        index = arc4random_uniform(self.cards.count);
        randomCard = self.cards[index];
    }
    randomCard.used = YES;
    return randomCard;
}

This methods gets called a lot (50'000 - 1'000'000 times for one monte-carlo-simulation)!
At the moment the whole thing is way to slow and I need really to optimize it. I have some Ideas:

• faster random number generator
• change the whole high-level representation of the deck (Objective-C Class including an NSArray of PlayingCards) and cards (Objective-C Class) to a representation in normal C-Arrays and structs
• change the whole representation of the deck and cards to the bitwise level and do everything down there

What do you think?
Do you have any other ideas?
Do you know a better suited (faster) random number generator?

Thanks in advance!

Answer 1

By randomly looking at the full deck in the loop

while (randomCard.isUsed) {

and not only the ones still in play, you will get a lot of retries when you reach the end of the deck. With the last card (number 52) giving > 25 misses on avareage. Treversing a full deck gives a total of more than 600 misses on average.

In adition to this, you also need to reset your deck before you can use it again. I guess you have a methode that resets the deck by looping through all the cards, and doing a used = NO. This gives 52 operations on the deck even if you only need to deal one card.

You can avoid both problems by this simple solution.

Store all your cards in an array. Then dedicate one end to cards not yet dealt, and the other end to cards that have been dealt:

                                                                                             <---------------------- not yet dealt ---------------------->
[ ah 2h 3h 4h 5h 6h 7h 8h 9h 10h jh qh kh ad 2d  ..... jk qk kk ]
                                                               ^
                                                            dealt 
                                                            cards

Randomly pick a card (7h) in the range of not yet dealt cards:

[ ah 2h 3h 4h 5h 6h 7h 8h 9h 10h jh qh kh ad 2d  ..... jk qk kk ]
                    ^^

Switch it with the last not yet dealt, and move the dealt card pointer on place left.

  <-------------------- not yet dealt --------------------->
[ ah 2h 3h 4h 5h 6h kk 8h 9h 10h jh qh kh ad 2d  ..... jk qk 7h ]
                                                            ^
                                                           dealt
                                                           cards

Repeat for as long as needed:

  <------------------ not yet dealt ----------------->
[ ah 2h qk 4h 5h 6h kk 8h 9h 10h jh jk kh ad 2d  ..... qh 3h 7h ]
                                                      ^
                                                    dealt 
                                                    cards

When you need a new deck, just move the dealt cards pointer back to the end, and the deck is ready for a new use.

  <----------------------- not yet dealt ---------------------->
[ ah 2h qk 4h 5h 6h kk 8h 9h 10h jh jk kh ad 2d  ..... qh 3h 7h ]
                                                               ^
                                                             dealt 
                                                             cards

The new order of the deck just adds to the randomness...

Answer 2

I assume you are calling this method multiple times to draw cards from a deck, setting the used property of the drawn card to YES so that it doesn't get drawn again.

Instead of setting the property, you can just remove the card from the deck and place it in a usedCards array, saving you the potentially never ending while loop.

Another approach would be to shuffle the deck initially, and then draw cards from the beginning or the end of the array.

Answer 3

Keep a static index pointing to the last card drawn (initially set to -1). Every time the method is invoked, advance the index modulo self.cards.count, and if the result is zero shuffle the deck. Then return the card at index. Since a decent shuffle such as Fisher-Yates/Knuth is Theta(self.cards.count) but gets invoked only one time out of self.cards.count, the result is amortized constant time per draw. This should avoid any overhead due to identifying already drawn values and rejecting. You could add a reset method if you want to avoid dealing out the whole deck before reshuffling.