distribuzione dei numeri casuali

Question

Ho due opzioni di codice:

Opzione 1

int myFunc() { 
    return new Random().nextInt(); 
} 

Oppure:

Opzione 2

private static final Random random = new Random(); 

int myFunc() { 
    return random.nextInt(); 
} 

capisco che option 2 è più idiomatico. Mi chiedo sulla validità di option 1.

In option 1 userò solo il primo numero generato da un seme specificato. In option 2 scelgo un seme e generi i numeri n usando quel seme. IIUC le garanzie sulla casualità sono su questo caso d'uso.

La mia domanda è, quindi, se chiamo option 1 molte volte ci sono garanzie sull'uniformità della distribuzione dell'output?

Answer 1

La mia vera domanda è se l'opzione 1 è matematicamente valida.

Iniziamo con opzione 2. Il generatore di numeri casuali utilizzato da java.util.Random è specificato nella javadoc come segue:

La classe utilizza un seme 48 bit, che viene modificato utilizzando una formula lineare congruenziale . (Vedere Donald Knuth, L'arte della Programmazione del computer, Volume 2, Sezione 3.2.1.)

e vi sono dettagli più specifici nei vari metodi 'javadocs.

Ma il punto è che stiamo usando una sequenza generata da una formula congruenziale lineare, e tali formule hanno un grado significativo di auto-correlazione ... che potrebbe essere problematico.

Ora con l'opzione 1, si utilizza un'altra istanza Random con un nuovo seme ogni volta e si applica un round della formula LC. Quindi stai ricevendo una sequenza di numeri che potrebbero essere autocorrelati con i semi. Tuttavia, i semi vengono generati in modi diversi, a seconda della versione di Java.

Java 6 fa questo:

public Random() { this(++seedUniquifier + System.nanoTime()); } 
private static volatile long seedUniquifier = 8682522807148012L; 

... che non è molto casuale a tutti. Se hai creato istanze Random a intervalli costanti, è probabile che i semi siano ravvicinati, e quindi la sequenza di numeri casuali prodotta dalla tua opzione # 1 può essere auto-correlata.

Al contrario, Java 7 e 8 fanno questo:

public Random() { 
    this(seedUniquifier()^System.nanoTime()); 
} 

private static long seedUniquifier() { 
    // L'Ecuyer, "Tables of Linear Congruential Generators of 
    // Different Sizes and Good Lattice Structure", 1999 
    for (;;) { 
     long current = seedUniquifier.get(); 
     long next = current * 181783497276652981L; 
     if (seedUniquifier.compareAndSet(current, next)) 
      return next; 
    } 
} 

private static final AtomicLong seedUniquifier 
    = new AtomicLong(8682522807148012L); 

La sequenza dei semi prodotti dalla cui sopra sono probabilmente un'approssimazione molto meglio (vero) casualità. Questo probabilmente rende l'opzione n. 1 superiore all'opzione n. 2.

Lo svantaggio dell'opzione n. 1 in Java da 6 a 8 è che la chiamata di System.nanoTime() probabilmente implica una chiamata di sistema. Questo è relativamente costoso.

---

Quindi la risposta breve è che è Java versione specifica quale di opzione # 1 e # 2 opzione produce una migliore qualità dei numeri "casuali" ... dal punto di vista matematico.

In entrambi i casi, la distribuzione dei numeri sarà uniforme su una dimensione di campione abbastanza grande, anche se non sono sicuro che sia significativo parlare di distribuzioni di probabilità quando il processo è deterministico.

Tuttavia, nessuno dei due metodi sarebbe adatto come generatore di numeri casuali di "forza crittografica".

Answer 2

Java inizializza il seme casuale con System.nanoTime() e un contatore sequenziale. Questo dà una certa garanzia che il seme sarà diverso per ogni invocazione, anche se mi asterrò dal chiamarlo crittograficamente sicuro.

Dal punto di vista delle prestazioni - si fa davvero aspettare di blocco sulla stato interno del caso in opzione 1 per avere un rendimento più grande ha colpito poi tutti i seguenti:

• l'accesso e incrementando volatili lungo
• ottenendo il tempo di sistema attuale (which is quite expensive)
• allocazione dinamica
• altro scopo garbage collection

Il mio suggerimento sarà di fare benchmark della vostra vera applicazione per scoprirlo, ma mi aspetto che l'opzione 1 sia la più lenta tra tutte e tre.

Answer 3

Quick Code:

// For occasional tasks that just need an average quality random number 
ExecutorService threadPool = Executors.newCachedThreadPool(); 
threadPool.execute(() -> { 
    ThreadLocalRandom.current().nextInt(); // Fast and unique! 
}); 


// For SecureRandom, high quality random number 
final Random r = new SecureRandom(); 
ExecutorService threadPool = Executors.newCachedThreadPool(); 
threadPool.execute(() -> { 
    r.nextInt(); // sun.security.provider.NativePRNG uses singleton. Can't dodge contention. 
}); 


// Apache Common Math - Mersenne Twister - decent and non-singleton 
int cpu = Runtime.getRuntime().availableProcessors(); 
ExecutorService executor = Executors.newFixedThreadPool(cpu); 
Map<Thread, RandomGenerator> random = new WeakHashMap<>(cpu, 1.0f); 

executor.execute(()-> { 
    RandomGenerator r; 
    synchronized (random) { // Get or create generator. 
     r = random.get(Thread.currentThread()); 
     if (r == null) random.put(Thread.currentThread(), r = new MersenneTwister()); 
    } 
    r.nextInt(1000); 
}); 

---

Spiegazione:

1. Due Random dello stesso seme produrrà stessi numeri.
   1. Quindi ci concentreremo su se possiamo garantire semi diversi.

2. In teoria, new Random() in ogni thread non garantisce seme diverso.

   1. nuovo caso è seminato da nanoTime e un numero "unico".
   2. Il numero non è garantito univoco perché il suo calcolo non è sincronizzato.
   3. Per quanto riguarda nanoTime, garantisce di essere "almeno buona come currentTimeMillis"
   4. currentTimeMillis non garantisce nulla e può essere prettycoarse.
   5. Nella vita reale, le due volte sono uguali solo su old linux systems and Win 98.

3. In pratica, new Random() in ogni thread fondamentalmente sempre ottenere diversi semi.

   1. La creazione di thread è costosa. Il mio crea 1 per 50.000 ns. E questo è notslow.
   2. 50μs è molto al di sopra delle granularità comuni di nanoTime fino a a few ten ns.
   3. Il calcolo del numero univoco (1.2) è anche veloce, quindi ottenere lo stesso numero è molto raro.
   4. Utilizzare Executors per creare un thread pool per evitare il pesante sovraccarico del nuovo thread.

4. zapl suggestedThreadLocalRandom.current().nextInt(). Grande idea.

   1. Non crea nuove Random, ma è anche un linear congruential generator.
   2. Genera un nuovo random per ogni thread di chiamata come seme di quel thread.
   3. È costruito per essere molto veloce in multi-thread. (Vedere le note di seguito.)
   4. È staticamente impostato da SecureRandom, che produce numeri casuali di qualità migliore.

5. "uniformemente distribuita" è solo una piccola parte di randomnesstests.

   1. Random è somewhat uniform, e il suo risultato può essere predicted dato solo due valori.
   2. SecureRandom garanzie this won't happens. (vale a dire crittograficamente forte)
   3. Non c'è alcun rischio di collisione se si crea un nuovo SecureRandom in ogni thread.
   4. Ma attualmente la sua origine è single thread in ogni caso, nessuna generazione parallela.
   5. Per un buon RNG che supporta il multi-thread, trovare external help come Apache Common MT.

Nota: Le modalità d'attuazione dedotte da Java 8 codice sorgente. La versione futura di Java potrebbe cambiare; ad esempio, utilizza sun.misc.Unsafe per memorizzare i semi, che may be removed in Java 9 forzando ThreadLocalRandom per trovare un nuovo modo di lavorare senza contesa.

Answer 4

Nella mia esperienza, il miglior bilanciamento tra buona distribuzione e prestazioni è dato dall'uso di un generatore tipo "Messerne Twister" (see in Apache Commons).Per una soluzione ancora più elaborata, vedi this.

Answer 5

No.

Non vi sono garanzie sulle proprietà della distribuzione dei numeri che saranno prodotti da Option 1. Come è stato chiarito in altre risposte, l'attuazione del costruttore per java.util.Random dipende il tempo di sistema. Pertanto, al fine di garantire le proprietà della distribuzione dei numeri che si ottengono con l'Opzione 1, è necessario essere in grado di fornire garanzie sulla distribuzione dei numeri prodotti dalle chiamate effettuate dal programma per ottenere l'ora del sistema su qualsiasi piattaforma su cui verrà eseguito il programma.

Con l'opzione 2, tuttavia, ci sono garanzie matematiche che possono essere fatte sulla distribuzione dei numeri che verranno prodotti durante una esecuzione del programma. Con un generatore di congruenza lineare (l'algoritmo di generazione del numero pseudocasuale usato da java.util.Random) alcune delle proprietà della casualità non sono altrettanto buone come con altri algoritmi, ma la distribuzione è garantita per essere relativamente uniforme.

Ciò non significa necessariamente che l'opzione 1 non possa servire ai propri scopi. Dipende da cosa stai facendo.