優化洗牌ArrayList

問題是：我需要洗牌一副牌（ArrayList或52個整數（0到51）數組）。我還需要在Android處理器上完成200,000次。請幫助我優化這一點，因爲即使在更高端的設備上（最多10秒），這也花費了令人難以置信的時間。優化洗牌ArrayList

方法我試過：

1）洗牌與Collections.shuffle和借鑑第一卡我得到（發生在Nexus7 8秒）：

for(long i = 0; i < ITERATIONS; i++) { // ITERATIONS is 200,000 
     ArrayList<Integer> fakeDeck = (ArrayList) deck.clone(); // deck is the sorted deck. 
     Collections.shuffle(fakeDeck); 
     int card1 = fakeDeck.get(0); 
     int card2 = fakeDeck.get(1); 
     int card3 = fakeDeck.get(2); 
     int card4 = fakeDeck.get(3); 
     int card5 = fakeDeck.get(4); 
     // do something with cards. 
}

2）隨機挑選從卡一個unshuffled甲板（好一點，需要5秒）：

for(long i = 0; i < ITERATIONS; i++) { // ITERATIONS is 200,000 
     ArrayList<Integer> fakeDeck = (ArrayList) deck.clone(); // deck is the sorted deck. 
     int card1 = pullCardFromDeck(fakeDeck); 
     int card2 = pullCardFromDeck(fakeDeck); 
     int card3 = pullCardFromDeck(fakeDeck); 
     int card4 = pullCardFromDeck(fakeDeck); 
     int card5 = pullCardFromDeck(fakeDeck); 
     // do something with cards. 
}

// pullCardFromDeck是：

private int pullCardFromDeck(ArrayList<Integer> deck) { 
    int randomNumber = new Random().nextInt(deck.size()); 
    int card = deck.get(randomNumber); // get a random card. 
    deck.remove(randomNumber); // remove the card from the deck. 
    return card; 
}

來源

2014-02-23 VM4

是否真的有必要每次克隆卡座？ – Radiodef

在第一個例子中，並不是必需的，我可以重新洗牌相同的套牌，在我需要的第二個例子中，因爲我刪除了紙牌。但這真的不是問題，因爲與洗牌相比，克隆只需要很少的時間。 – VM4

'隨便'不便宜。將它移到循環之外並傳遞給您的方法。 – Jeffrey

如果你只需要5張牌，每次只能洗牌5張牌。這可能快20倍。

public static void main(String... ignored) { 
    int[] cards = new int[52]; 
    for (int i = 0; i < cards.length; i++) cards[i] = i; 

    long start = System.currentTimeMillis(); 
    int runs = 1000000; 
    for (int i = 0; i < runs; i++) { 
     shuffleN(cards, 5); 
     int card1 = cards[0], card2 = cards[1], card3 = cards[2], card4 = cards[3], card5 = cards[4]; 
    } 
    long time = System.currentTimeMillis() - start; 
    System.out.printf("Took %.3f seconds to shuffle %,d times%n", time/1e3, runs); 
} 

private static final Random RND = new Random(); 

public static void shuffleN(int[] numbers, int count) { 
    for (int i = 0; i < count; i++) { 
     int r = RND.nextInt(numbers.length - i) + i; 
     if (i == r) continue; 
     int tmp = numbers[i]; 
     numbers[i] = numbers[r]; 
     numbers[r] = tmp; 
    } 
}

打印

Took 0.115 seconds to shuffle 1,000,000 times

來源

2014-02-23 20:16:35

我需要從52張牌組中抽出5張牌。 – VM4

@VM所以你會計數5，前5張卡片是隨機的，即使其餘的卡片不會很隨機。即這就像一個洗牌，但在前5張牌後停止，使其速度提高10倍。 –

我不明白，你不是每次都換5張牌嗎？這會產生相同的結果。對不起，我很慢。 – VM4

你可能會更好使用INT的指數[]你洗牌和用於訪問一個單一的甲板考慮。爲了獲得隨機條目，將選擇的索引設置爲零（並且當你得到一個隨機數時，看看這個數值是否爲零，如果是選擇一張新卡）

來源

2014-02-23 20:19:49 ErstwhileIII

優化洗牌ArrayList

回答

相關問題