Generatore di numeri casuali a distribuzione uniforme molto veloce

Question

Come parte di una simulazione Monte Carlo, devo tirare un gruppo di dadi finché certi valori non vengono visualizzati un certo numero di volte. Il mio codice che fa questo chiama una classe di dadi che genera un numero casuale compreso tra 1 e 6 e lo restituisce. Originariamente il codice sembrava

public void roll() { 
    value = (int)(Math.random()*6) + 1; 
} 

e non era molto veloce. Attraverso lo scambio di Math.random() per

ThreadLocalRandom.current().nextInt(1, 7); 

Correva una sezione in circa il 60% del tempo originale, che ha chiamato questo in tutto circa 250 milioni di volte. Come parte della simulazione completa invocherà questo metodo per un minimo di miliardi di volte, quindi c'è un modo più veloce per farlo?

Answer 1

Scegli un generatore casuale che sia il più veloce e buono che tu abbia bisogno di essere, e che non sia rallentato a una minima frazione della sua velocità normale dai meccanismi di sicurezza del filo. Quindi scegli un metodo per generare la distribuzione di interi [1..6] che sia veloce e precisa quanto necessario.

La semplice generatore veloce che è di qualità sufficientemente elevata da battere test standard per PRNGs come TestU01 (invece di omettere sistematicamente, come il Mersenne Twister) è Sebastiano Vigna'sxorshift64*. Sto mostrando come codice C, ma Sebastiano lo ha in Java as well:

uint64_t xorshift64s (int64_t &x) 
{ 
    x ^= x >> 12; 
    x ^= x << 25; 
    x ^= x >> 27; 

    return x * 2685821657736338717ull; 
} 

Sebastiano Vigna's site ha un sacco di informazioni utili, link e risultati di benchmark. Comprese le carte, per l'inclinazione matematica.

A quella alta risoluzione si può semplicemente usare 1 + xorshift64s(state) % 6 e il bias sarà incommensurabilmente piccolo. Se non è abbastanza veloce, implementa la divisione modulo per moltiplicazione con l'inverso. Se questo non è abbastanza veloce - se non puoi permetterti due MUL per ogni variazione - allora diventa complicato e devi tornare qui. xorshift1024* (Java) e alcuni trucchetti per la variabile potrebbero essere un'opzione.

Batching: la generazione di un array pieno di numeri e l'elaborazione, quindi il riempimento della matrice e così via, possono sbloccare alcune riserve di velocità. Avvolgere le cose in modo inutile nelle classi realizza il contrario.

P.S .: se ThreadLocalRandom e xorshift * non sono abbastanza veloci per i tuoi scopi, anche con il batching, potresti fare delle cose nel modo sbagliato, oppure potresti farlo nella lingua sbagliata. O entrambi.

P.P.S .: in lingue come Java (o C# o Delphi), l'astrazione non è gratuita, ha un costo. In Java devi anche fare i conti con cose come il controllo obbligatorio dei limiti dell'array gratuito, a meno che tu non abbia un compilatore in grado di eliminare quei controlli. Prendere in giro le prestazioni elevate da un programma Java può essere molto complicato ... In C++ ottieni gratuitamente astrazione e prestazioni.

Answer 2

Darth è corretto che Xorshift * è probabilmente il miglior generatore da utilizzare. Usalo per riempire un buffer circolare di byte, quindi recupera i byte uno alla volta per tirare i dadi, ricarica il buffer quando hai recuperato abbastanza. Per ottenere il tiro di dado effettivo, evitare la divisione e il bias utilizzando il campionamento del rifiuto. Il resto del codice è quindi qualcosa di simile (in C):

do { 
    if (bp >= buffer + sizeof buffer) { 
     // refill buffer with Xorshifts 
    } 
    v = *bp++ & 7; 
} while (v > 5); 
return v; 

Questo vi permetterà di ottenere in media 6 tiri di dado per 64-bit valore casuale.