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...