Pertinente al fatto che rand() % n è inferiore all'ideale
Il fare rand() % n ha una distribuzione non uniforme. Otterrai un numero sproporzionato di determinati valori perché il numero di valori non è un multiplo di 20
Successivamente, rand() è in genere un generatore congruenziale lineare (ci sono molti altri , solo questo è il più probabile implementato - e con parametri meno che ideali (ci sono molti modi per selezionare i parametri)). Il problema più grande è che spesso i bit bassi (quelli che si ottengono con un'espressione di tipo % 20 ) non sono casuali. Ricordo un rand() di anni fa in cui il bit più basso si è alternato da 1 a 0 con ogni chiamata a rand() - non era molto casuale.
Dalla rand (3) pagina man:
The versions of rand() and srand() in the Linux C Library use the same
random number generator as random() and srandom(), so the lower-order
bits should be as random as the higher-order bits. However, on older
rand() implementations, and on current implementations on different
systems, the lower-order bits are much less random than the higher-
order bits. Do not use this function in applications intended to be
portable when good randomness is needed.
Questo potrebbe essere ora relegato alla storia, ma è abbastanza probabile che tu abbia ancora un'implementazione povera di rand () che si nasconde da qualche parte nello stack. Nel qual caso, è ancora abbastanza applicabile.
La cosa da fare è usare effettivamente una buona libreria di numeri casuali (che dà buoni numeri casuali) e poi chiedere numeri casuali all'interno dell'intervallo desiderato.
Un esempio di un buon numero di bit di codice casuale (dalle 13:00 nel video collegato)
#include <iostream>
#include <random>
int main() {
std::mt19937 mt(1729); // yes, this is a fixed seed
std::uniform_int_distribution<int> dist(0, 99);
for (int i = 0; i < 10000; i++) {
std::cout << dist(mt) << " ";
}
std::cout << std::endl;
}
Confronta questo per:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
srand(time(NULL));
for (int i = 0; i < 10000; i++) {
printf("%d ", rand() % 100);
}
printf("\n");
}
Esegui entrambi questi programmi e confronta la frequenza con cui alcuni numeri vengono visualizzati (o non vengono visualizzati) in quell'output.
Video correlato: rand () considerato dannoso
Alcuni aspetti storici di rand () che causano bug in Nethack che si dovrebbero osservare e considerare nelle proprie implementazioni:
-
Problema RNG di Nethack
Rand() is a very fundamental function for Nethack's random number generation. The way Nethack uses it is buggy or it may be argued that lrand48() produces crappy pseudo-random numbers. (However, lrand48() is a library function using a defined PRNG method and any program that uses it should take into account the weaknesses of that method.)
The bug is that Nethack relies (sometimes exclusively as is the case in rn(2)) on the lower bits of the results from lrand48(). Because of this, RNG in the whole game works bad. This is especially noticable before user actions introduce further randomness, i.e. in character generation and first level creation.
Anche se il precedente era del 2003, dovrebbe comunque essere tenuto presente poiché potrebbe non essere il caso che tutti i sistemi che eseguono il gioco previsto siano un sistema Linux aggiornato con una buona funzione rand (). / p>
Se stai facendo questo per te stesso, puoi verificare quanto è buono il tuo generatore di numeri casuali tramite scrivere un codice e testare l'output con ent .
Sulle proprietà dei numeri casuali
Ci sono altre interpretazioni di "random" che non sono esattamente casuali. In un flusso casuale di dati, è possibile ottenere lo stesso numero due volte. Se si lancia una moneta (casuale), è abbastanza possibile ottenere due teste di fila. Oppure lancia un dado due volte e ottieni lo stesso numero due volte di seguito. Oppure girare una ruota della roulette e ottenere lo stesso numero due volte lì.
La distribuzione dei numeri
Quando si riproduce un elenco di brani, le persone si aspettano che "random" significhi che la stessa canzone o artista non verrà riprodotto una seconda volta di seguito. Avere una playlist su The Beatles per due volte consecutive è considerata "non casuale" (anche se è casuale). La percezione che per una playlist di quattro brani suonasse un totale di otto volte:
1 3 2 4 1 2 4 3
è più "casuale" di:
1 3 3 2 1 4 4 2
Altro su questo per il "mescolamento" di canzoni: Come mescolare le canzoni?
Su valori ripetuti
Se non vuoi ripetere valori, c'è un approccio diverso che dovrebbe essere considerato. Genera tutti i valori possibili e mescolali.
Se stai chiamando rand() (o qualsiasi altro generatore di numeri casuali), lo stai chiamando con la sostituzione. Puoi sempre ottenere lo stesso numero due volte. Un'opzione è di buttare via i valori ancora e ancora finché non ne selezioni uno che soddisfi i tuoi requisiti. Farò notare che questo ha un runtime non deterministico ed è possibile che tu ti possa trovare in una situazione in cui c'è un ciclo infinito a meno che non inizi a fare un backtracing più complesso.
Elenca e seleziona
Un'altra opzione è quella di generare un elenco di tutti gli stati validi possibili e quindi selezionare un elemento casuale da quella lista. Trova tutti i punti vuoti (che soddisfano alcune regole) nella stanza e poi sceglierne uno casuale da quella lista. E poi fallo ancora e ancora finché non hai finito.
Shuffle
L'altro approccio è mescolare come se fosse un mazzo di carte. Inizia con tutti i punti vuoti nella stanza e poi inizia ad assegnarli distribuendo i punti vuoti, uno alla volta, a ogni regola / processo che richiede un posto vuoto. Hai finito quando finisci le carte o le cose smettono di chiederle.