2013-03-19 17 views
40

Ho letto che molti generatori di numeri pseudo-casuali richiedono molti campioni in ordinato di essere "riscaldato". È questo il caso quando usi std :: random_device per seminare std :: mt19937, o possiamo aspettarci che sia pronto dopo la costruzione? Il codice in questione:std :: mt19937 richiede il riscaldamento?

#include <random> 
std::random_device rd; 
std::mt19937 gen(rd()); 
+7

Dove l'hai letto? Non ho mai sentito parlare, tutto quello che so è che essi dovrebbero essere testa di serie ... – PlasmaHH

+0

Ad esempio, v'è una certa discussione in questo documento: http://www0.cs.ucl.ac.uk/staff/d. jones/GoodPracticeRNG.pdf – Brent

+1

Per la maggior parte dei PRNG questo non ha assolutamente senso. La semina imposta lo stato interno e qualsiasi "riscaldamento" permuta lo stato interno, in quanto tale ha lo stesso identico effetto se questo nuovo stato fosse stato scelto come seme. – PlasmaHH

risposta

51

Mersenne Twister è un turno -register basato PRNG (pseudo-generatore di numeri casuali) ed è quindi soggetto a cattive semi con lunghi tratti di 0 o 1 che portano a risultati relativamente prevedibili finché lo stato interno è mescolato abbastanza.

Tuttavia il costruttore che prende un singolo valore utilizza una funzione complessa su quel valore di seme che è progettato per minimizzare la probabilità di produrre tali stati 'cattivi'. C'è un secondo modo per inizializzare mt19937 in cui si imposta direttamente lo stato interno, tramite un oggetto conforme al concetto SeedSequence. È questo secondo metodo di inizializzazione in cui potrebbe essere necessario preoccuparsi della scelta di uno stato "buono" o del riscaldamento.


Lo standard include un oggetto conforme al concetto SeedSequence, chiamato seed_seq. seed_seq prende un numero arbitrario di valori di inizializzazione di ingresso, e poi esegue alcune operazioni su tali valori per produrre una sequenza di valori diversi adatti per impostare direttamente lo stato interno di un PRNG.

Ecco un esempio di caricamento di una sequenza di seme con dati casuali sufficienti per riempire l'intero stato std::mt19937:

std::array<int, 624> seed_data; 
std::random_device r; 
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r)); 
std::seed_seq seq(std::begin(seed_data), std::end(seed_data)); 

std::mt19937 eng(seq); 

Questo assicura che l'intero stato è randomizzato. Inoltre, ogni motore specifica la quantità di dati letti da seed_sequence in modo che tu possa leggere i documenti per trovare tali informazioni per qualsiasi motore tu usi.

Anche se qui carico completamente seed_seq da std::random_device, seed_seq è specificato in modo tale che solo alcuni numeri che non sono particolarmente casuali dovrebbero funzionare bene. Per esempio:

std::seed_seq seq{1, 2, 3, 4, 5}; 
std::mt19937 eng(seq); 

nei commenti qui sotto Cubbi indica che seed_seq opere di eseguire una sequenza di riscaldamento per voi.

Ecco quello che dovrebbe essere il tuo 'default' per la semina:

std::random_device r; 
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()}; 
std::mt19937 rng(seed); 
+2

Per coincidenza, il predefinito C++ 11 'seed_seq' * è * la sequenza di riscaldamento di Mersenne Twister (anche se le implementazioni esistenti,' mt19937' di libC++, usano un riscaldamento più semplice quando viene fornito un seme a valore singolo) – Cubbi

+1

'std :: generate_n' genera SDL Warning C4996 sui nuovi compilatori MSVC in modo da poter usare 'std :: generate (seed_data.begin(), seed_data.end(), std :: ref (r)) ;, invece. – NightElfik

+0

È sicuro assumere che il 'state_size' di un generatore è sempre espresso in multipli di' sizeof (int) '? Se un generatore avesse un 'state_size' misurato in byte, ad esempio, l'array' seed_data' sarebbe troppo grande. – Wyzard

2

Credo ci sono situazioni in cui MT può essere seminati "poco", che si traduce in sequenze non ottimali. Se ricordo bene, la semina con tutti gli zeri è uno di questi casi. Ti consiglierei di provare a usare i generatori WELL se questo è un problema serio per te. Credo che siano più flessibili: la qualità del seme non ha importanza. (Forse per rispondere alla tua domanda più direttamente: è probabilmente più efficiente concentrarsi sul seeding piuttosto che sul seeding male cercando di generare un gruppo di campioni per portare il generatore a uno stato ottimale.)