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

このメソッドは何度も呼び出されます (1 回のモンテカルロ シミュレーションで 50,000 ～ 1,000,000 回)。
現時点では全体が遅くなっており、最適化する必要があります。私にはいくつかのアイデアがあります：

  • より高速な乱数ジェネレーター
  • デッキ (PlayingCards の NSArray を含む目的の C クラス) とカード (目的の C クラス) の高レベルの表現全体を、通常の C 配列と構造体の表現に変更します。
  • デッキとカードの表現全体をビットごとのレベルに変更し、そこですべてを行います

どう思いますか？
他にアイデアはありますか？
より適した (より高速な) 乱数ジェネレーターを知っていますか?

前もって感謝します！

4

3 に答える 3

2

ループ内のデッキ全体をランダムに見ることによって

while (randomCard.isUsed) {

まだ場にあるものだけでなく、デッキの最後に到達すると、多くの再試行が行われます。最後のカード (52 番) では、平均で 25 回以上のミスが発生します。フルデッキをトレバースすると、合計で平均600 回以上のミスが発生します。

これに加えて、再度使用する前にデッキをリセットする必要があります。すべてのカードをループしてデッキをリセットする方法があると思いますused = NO。これにより、カードを 1 枚しか配らなくても、デッキで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 に設定されています)。メソッドが呼び出されるたびに、 index modulo を進め、self.cards.count結果がゼロの場合はデッキをシャッフルします。次に、カードをインデックスに戻します。Fisher-Yates/Knuth などのまともなシャッフルは Theta( self.cards.count) ですが、 から 1 回しか呼び出されないself.cards.countため、結果は描画ごとに一定時間償却されます。これにより、すでに描画された値を識別して拒否することによるオーバーヘッドを回避できます。再シャッフルの前にデッキ全体を配るのを避けたい場合は、reset メソッドを追加できます。

于 2013-09-28T18:37:25.237 に答える