La scelta di numeri casuali in modo efficiente

Question

Ho un metodo, che utilizza campioni casuali per approssimare un calcolo. Questo metodo viene chiamato milioni di volte, quindi è molto importante che il processo di scelta dei numeri casuali è efficiente.

Non sono sicuro di quanto velocemente Random().nextInt Javas sono davvero, ma il mio programma non sembra beneficiare tanto quanto mi piacerebbe anche.

Al momento di scegliere i numeri casuali, faccio la seguente (in semi pseudo-codice):

// Repeat this 300000 times
Set set = new Set();
while(set.length != 5)
    set.add(randomNumber(MIN,MAX));

Ora, questo ha ovviamente un brutto caso peggiore tempo di esecuzione, come il caso-funzione nella teoria può aggiungere numeri duplicati per un'eternità, rimanendo in tal modo nel ciclo while per sempre. Tuttavia, i numeri vengono scelti da {0..45}, quindi un valore duplicato è per la maggior parte poco probabile.

Quando uso il metodo di cui sopra, il suo solo il 40% più veloce rispetto al mio altro metodo, che non approssimativa, ma produce il risultato corretto. Questo è gestito ~ 1 milione di volte, quindi mi aspettavo questo nuovo metodo per essere almeno il 50% più veloce.

Hai qualche suggerimento per un metodo più veloce? O forse siete a conoscenza di un modo più efficiente di generazione di un insieme di numeri casuali.

Per chiarire, ecco i due metodi:

// Run through all combinations (1 million). This takes 5 seconds
 for(int c1 = 0; c1 < deck.length; c1++){
    for(int c2 = c1+1; c2 < deck.length; c2++){
     for(int c3 = c2+1; c3 < deck.length; c3++){
        for(int c4 = c3+1; c4 < deck.length; c4++){
         for(int c5 = c4+1; c5 < deck.length; c5++){
             enumeration(hands, cards, deck, c1, c2, c3, c4, c5);
         }
            } 
      }     
   }
   }

// Approximate (300000 combinations). This takes 3 seconds
Random rand = new Random();
HashSet<Integer> set = new HashSet<Integer>();
int[] numbers = new int[5];
while(enumerations < 300000){
set.clear();
while(set.size() != 5){
    set.add(rand.nextInt(deck.length));
}
Iterator<Integer> i = set.iterator();
int n = 0;
while(i.hasNext()){
    numbers[n] = i.next();
    n++;
}

Dopo qualche test e profiling, ho trovato questo metodo per essere il più efficace:

Random rand = new Random();
int[] numbers = new int[5];
ArrayList<Integer> list = new ArrayList<Integer>();
while(enumerations < 300000){
 while(list.size() != 5) {
     int i = rand.nextInt(deck.length);
        if(!list.contains(i)) list.add(i);
 }
 int index = 0;
 for(int i : list){ numbers[index] = i; index++; }
 enumeration(hands, cards, deck,numbers);
}

Answer 1

Si può provare a utilizzare un esistente implementazione Java ( o questa ) per un Mersenne Twister .

Tenete a mente più di MT sono non crittograficamente sicuro.

Answer 2

Sembra che si desidera selezionare un k - combinazione da un insieme S senza sostituzione, con S avente n valori distinti, k = 5 e n = 52. È possibile shuffle() l'intero set e selezionare k elementi (come suggerisce @Tesserex), o pick() k elementi, evitando duplicati (come hai mostrato). Avrai voglia di profilo sia in un ambiente particolare e per il vostro generatore di scelta. Mi capita spesso, ma non sempre, vedo un vantaggio modesto per pick().

private static final Random rnd = new Random();
private static final int N = 52;
private static final int K = 5;
private static final List<Integer> S = new ArrayList<Integer>(N);
static {
    for (int i = 0; i < N; i++) {
        S.add(i + 1);
    }
}
private final List<Integer> combination = new ArrayList<Integer>(K);

...

private void shuffle() {
    Collections.shuffle(S, rnd);
    combination.addAll(S.subList(0, K));
}

private void pick() {
    for (int i = 0; i < K; i++) {
        int v = 0;
        do {
            v = rnd.nextInt(N) + 1;
        } while (combination.contains(v));
        combination.add(v);
    }
}

Answer 3

Una tecnica comune è quella di iniziare con un elenco di tutti i possibili ingressi, e selezionerà casualmente a questo, la cancellazione di quelli, come si va. In questo modo non c'è rischio di selezionare un duplicato e di dover ciclo per un importo di tempo indeterminato. Naturalmente questo metodo funziona solo con i dati discreti, ma per fortuna sono interi. Ricorda inoltre che la vostra lista (o altra struttura di dati) la selezione e la cancellazione deve essere O (1), se possibile, dal momento che si sta concentrando sulla velocità.

Answer 4

Si potrebbe utilizzare congruenza lineare come un generatore casuale: http://en.wikipedia.org/wiki / Linear_congruential_generator [ancora considerare i loro svantaggi statistici]

Hai solo bisogno di un calcolo di (x + c)% m per ogni numero. Eppure, nella mia esperienza la creazione di oggetti (come si potrebbe fare con ogni chiamata di nuovo Set e aggiungere, a seconda di quale applicazione si utilizza) potrebbe costare più velocità di una chiamata a nextInt (). Forse si dovrebbe cercare un profiler come ad esempio questo: http://www.eclipse.org/tptp/

Answer 5

Non ho alcun input sul problema reale, e non so troppo Java (solo rovistando). Tuttavia mi sembra che si sta tentando di costruire un valutatore mano per il poker e questa discussione http://pokerai.org/pf3/viewtopic.php?f=3&t=16 contiene alcuni valutatori java mano estremamente veloci. Speriamo che alcuni di questo codice potrebbe essere di aiuto.

Answer 6

Se sei stato rallentato dal fatto che si deve saltare i duplicati, si potrebbe risolvere il problema con la creazione di un elenco di tutti i valori delle carte, e quindi la rimozione dalla lista, come vengono selezionate le carte e la scelta di un caso numero in una gamma più ridotta la prossima volta. Qualcosa di simile a questo:

// Assuming we're just numbering all the cards 0 to 51. This could be more sophisticated, of course.
ArrayList cards=new ArrayList(52);
for (int x=0;x<52;++x)
  cards=new Integer(x);

Integer[] hand=new Integer[5];
for (int h=0;h<5;++h)
{
  // Pick a card from those remaining
  int n=random.nextInt(cards.size());
  hand[h]=cards.get(n);
  // Remove the picked card from the list
  cards.remove(n);
}

Per la prima estrazione, cards.get (n) restituirà n, non importa quale n è. Ma da quel momento in poi, i valori saranno rimossi in modo cards.get (3) potrebbe restituire 7, ecc.

La creazione della lista e la rimozione da esso aggiunge un po 'di testa. La mia ipotesi è che se si sta raccogliendo solo 5 carte alla volta, la probabilty di collisioni è abbastanza piccolo che eliminando duplices Dopo aver trovato loro sarebbe più veloce di prevenirli. Anche l'ultimo pareggio, la probabilità di un duplicato è solo 4/52 = 1/13, quindi faresti raramente colpisce un duplicato a tutti e la probabilità che 2 pareggi di fila sarebbero entrambi i duplicati sarebbe molto piccolo. Tutto dipende da quanto tempo ci vuole per generare un numero casuale rispetto a quanto tempo ci vuole per impostare l'array e fare le rimuove. Il modo più semplice per dire sarebbe quella di fare qualche esperimento e misurare. (O profilo!)

Answer 7

Non indovinare, misurare sempre.

 long time = System.getCurrentMilliseconds();
 Random().nextInt()
 System.out.println(System.getCurrentMilliseconds() - time);

Inoltre, non si dovrebbe mai fare affidamento su come infrequente un bug noto accadrà, basta codice defensivley quindi non è così. Rilevare un duplicato, e se si tratta di un duplicato allora non aggiungerlo, e saltare l'iterazione con una dichiarazione continue.

Per quanto riguarda i metodi più veloci e numeri casuali ... Non è possibile ottenere numeri casuali in Math.random() di Java. Si può ottenere solo numeri pseudo casuali. Quanto velocemente si desidera che questo sia arriva al sacrificio di come apparentemente casuale è necessario per loro apparire. Il modo più veloce per generare un numero pseudo-casuale comporterebbe po spostamento e inoltre in base al valore del seme, come System.getCurrentMilliSeconds() Inoltre, pseudo-casuali generazione di numeri è già abbastanza veloce in quanto è l'aritmetica CPU solo cruda comunque, quindi probabilmente sarete abbastanza felice una volta si vede quanti millisecondi che serve per generare uno con Math.random().

Answer 8

Non cercare di sviluppare il vostro generatore di num casuali noto. Utilizzare uno noto come SecureRandom invece:

http://www.owasp.org/index.php/Using_the_Java_Cryptographic_Extensions