1

目前我正在开发一个 iOS 应用程序，我需要从卡片组中随机抽取卡片。目前我的代码如下所示：

- (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;
}

这种方法被调用了很多（50'000 - 1'000'000 次蒙特卡罗模拟）！
目前整个事情都变慢了，我真的需要优化它。我有一些想法：

  • 更快的随机数生成器
  • 将牌组（Objective-C 类，包括 NSArray of PlayingCards）和卡片（Objective-C 类）的整个高级表示更改为普通 C 数组和结构中的表示
  • 将甲板和卡片的整个表示更改为按位级别并在那里做所有事情

你怎么看？
你还有其他建议吗？
您知道更适合（更快）的随机数生成器吗？

提前致谢！

4

3 回答 3

2

通过随机查看循环中的完整套牌

while (randomCard.isUsed) {

不仅是仍在玩的那些，当你到达甲板的尽头时，你会得到很多重试。最后一张牌（52 号）的平均失误数 > 25。遍历一个完整的甲板平均会造成超过600 次失误。

除此之外，您还需要重置您的牌组，然后才能再次使用它。我猜你有一个方法可以通过循环遍历所有卡片来重置套牌，然后执行used = NO. 即使您只需要发一张牌，这也可以在甲板上进行52 次操作。

您可以通过这个简单的解决方案避免这两个问题。

将所有卡片存储在一个数组中。然后将一端用于尚未发牌，另一端用于已发牌：

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

在尚未发牌的范围内随机选择一张牌（7h）：

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

将其与最后一张尚未发牌的牌交换，并将发牌指针移至左侧。

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

根据需要重复：

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

当您需要新牌组时，只需将发牌指针移回末端，牌组就可以重新使用了。

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

牌组的新顺序只是增加了随机性......

于 2013-09-28T22:30:01.700 回答
0

我假设您多次调用此方法从一副牌中抽牌，used将抽牌的属性设置为YES使其不再被抽牌。

无需设置属性，您只需从牌组中取出卡片并将其放入usedCards数组中，从而为您节省可能永无止境的while循环。

另一种方法是先洗牌，然后从阵列的开头或结尾抽牌。

于 2013-09-28T11:21:24.730 回答
0

保持一个指向最后一张牌的静态索引（最初设置为 -1）。每次调用该方法时，将索引模前移self.cards.count，如果结果为零，则将牌组洗牌。然后在索引处返回卡。由于像 Fisher-Yates/Knuth 这样的体面洗牌是 Theta( self.cards.count)，但在 中只被调用一次self.cards.count，因此结果是每次平局的摊销常数时间。这应该避免由于识别已经绘制的值和拒绝而导致的任何开销。如果您想避免在重新洗牌前将整副牌发完，您可以添加一个重置方法。

于 2013-09-28T18:37:25.237 回答