java - 优化改组 ArrayList

Question

问题是这样的:我需要洗一副纸牌(ArrayList 或 52 个整数(0 到 51)的数组)。我还需要在 Android 处理器上执行此操作 200,000 次。请帮我优化这个，因为即使在更高端的设备上(最多 10 秒)，这也会花费令人难以置信的时间。

我尝试过的方法:

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) 从一副未洗牌的牌中随机抽牌(好一点，需要 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;
}

Answer 1

如果您只需要五张牌，则每次只需洗 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