從撲克牌中抽牌以獲得撲克的蒙特卡羅模擬

目前我正在研究一個iOS應用程序，我需要從一個carddeck中抽取隨機卡。目前我的代碼看起來是這樣的：從撲克牌中抽牌以獲得撲克的蒙特卡羅模擬

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

這個方法被調用了很多（50000 - 1'000'000次爲一蒙特卡羅仿真）！
目前整個事情都是慢下來的，我真的需要優化它。我有一些想法：

更快的隨機數發生器
變化甲板（Objective-C類，包括PlayingCards的一個NSArray）和卡（Objective-C類），以一個全高級別表示在正常的C-數組和結構
變化的甲板和卡位單位水平的整體表現表示並盡一切那裏

你覺得呢？
你有任何其他想法？
你知道一個更適合（更快）的隨機數發生器嗎？

在此先感謝！

來源

2013-09-28 Robin de Bois

通過在循環

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-28 22:30:01

我改變了我的實現，並且它工作正常！謝謝！你有另一個想法來獲得更多的速度？ –

現在它有多快？什麼部分花時間？ –

那麼，如果你使用解決方案，也許你可以接受答案？ –

我假設你多次調用這個方法來從卡組中抽取卡牌，將被抽取的卡牌的used屬性設置爲YES，這樣它就不會再被抽出。

除了設置屬性，您可以從卡組中移除卡並將其放置在usedCards陣列中，從而爲您節省潛在永不止息的while循環。

另一種方法是最初洗牌，然後從陣列的開始或結束抽取牌。

來源

2013-09-28 11:21:24 Sebastian

這樣做的原因是執行，我要吸取些（2 - 23）卡在甲板的，做一些計算，然後重新設置套牌，並一次又一次地做這一切（50'000 - 1'000'000次）...所以我不知道你的建議是否會加快速度。因爲我認爲創建一個NSArray的開銷，應對一些元素，複製元素（重置）比僅僅設置一些布爾值，以及設置布爾值以重置......你能解釋爲什麼你認爲它會有幫助嗎？ –

看起來你的while循環並不像我想象的那麼嚴重（除非畫卡數量非常接近甲板尺寸）。 – Sebastian

保持一個靜態索引指向最後繪製的卡片（最初設置爲-1）。每次該方法被調用時，提前索引模self.cards.count，如果結果爲零，則洗牌。然後將該卡返回索引。由於像Fisher-Yates/Knuth這樣的體面洗牌是Theta（self.cards.count），但在self.cards.count中只有一次被調用，所以結果是攤牌每次平均時間。這應該避免由於識別已經繪製的值和拒絕而導致的任何開銷。如果您想避免在重新洗牌之前處理整個套牌，您可以添加重置方法。

來源

2013-09-28 18:37:25 pjs

從撲克牌中抽牌以獲得撲克的蒙特卡羅模擬

回答

相關問題