Come devo testare la casualità?

Non penso che i test unitari siano lo strumento giusto per testare la casualità. Un test unitario dovrebbe chiamare un metodo e testare il valore restituito (o lo stato dell'oggetto) rispetto a un valore previsto. Il problema con la verifica della casualità è che non esiste un valore previsto per la maggior parte delle cose che vorresti testare. Puoi testare con un seme dato, ma questo test solo ripetibilità . Non ti dà alcun modo per misurare quanto a caso è la distribuzione, o se è addirittura casuale a caso.

Fortunatamente ci sono molti test statistici che puoi eseguire, come la Batteria dura di test di casualità . Vedi anche:

1. Come testare un generatore di numeri pseudo casuali?

   • Steve Jessop ti consiglia di trovare un'implementazione testata dello stesso algoritmo RNG che stai utilizzando e confrontare il suo output con semi selezionati contro la tua stessa implementazione.
   • Greg Hewgill raccomanda ENT suite di test statistici.
   • John D. Cook rimanda i lettori al suo articolo CodeProject Generazione di numeri casuali semplici , che include un'implementazione del test di Kolmogorov-Smirnov menzionato nel volume 2 di Donald Knuth, Algoritmi seminali.
   • Diverse persone consigliano di testare che la distribuzione dei numeri generati sia uniforme, il test del chi quadrato e che la media e la deviazione standard rientrino nell'intervallo previsto. (Nota che testare la distribuzione da sola non è sufficiente. [1,2,3,4,5,6,7,8] è una distribuzione uniforme, ma non è certamente casuale.)

2. Test unitario con funzioni che restituiscono risultati casuali

   • Brian Genisio sottolinea che prendersi gioco del tuo RNG è un'opzione per rendere ripetibili i tuoi test e fornisce codice di esempio C #.
   • Ancora una volta, molte altre persone puntano a utilizzare valori di seme fissi per ripetibilità e test semplici per una distribuzione uniforme, Chi quadrato, ecc.

3. Unit Testing Randomness è un articolo wiki che parla di molte delle sfide già affrontate quando si prova a testare ciò che è, per sua natura, non ripetibile. Un aspetto interessante che ho raccolto è stato il seguente:

   I've seen winzip used as a tool to measure the randomness of a file of values before (obviously, the smaller it can compress the file the less random it is).

1. Unit test il tuo algoritmo

Per la prima domanda vorrei creare una classe falsa che tu nutrite una sequenza di numeri casuali per i quali conosci il risultato del tuo algoritmo. In questo modo ti assicuri che l'algoritmo che costruisci in cima della tua funzione casuale funzioni. Quindi qualcosa sulla falsariga di:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Verifica se la tua funzione casuale ha senso

Al test dell'unità è necessario aggiungere un test che viene eseguito più volte e asserisce che i risultati

• sono entro i limiti che hai impostato (quindi, un tiro di dado è compreso tra 1 e 6) e
• mostra una distribuzione sensata (esegui più esecuzioni di test e verifica se la distribuzione è all'interno di x% di quanto ti aspettavi, ad esempio per il lancio dei dadi dovresti vedere un 2 salire tra il 10% e il 20% (1/6 = 16.67%) del tempo dato che lo hai rotolato 1000 volte).

3. Test di integrazione per l'algoritmo e la funzione casuale

Quanto spesso ti aspetteresti che il tuo array sia ordinato nell'ordinamento originale? Ordina un paio di centinaia di volte e asserisci che solo x% delle volte l'ordinamento non cambia.

Questo è già un test di integrazione, stai testando l'algoritmo insieme alla funzione casuale. Una volta che usi la funzione casuale reale, non puoi più scappare con le singole prove di prova.

Dall'esperienza (ho scritto un algoritmo genetico) direi che combinando il test unitario del tuo algoritmo, il test di distribuzione della tua funzione casuale e il test di integrazione è la strada da percorrere.

Un aspetto dei PRNG che sembra dimenticato è che tutte le sue proprietà sono di natura statistica: non ci si può aspettare che mischiare una matrice porti a una permutazione diversa da quella con cui si è iniziato. In sostanza, se si utilizza un PRNG normale, l'unica cosa che si è certi è che non usa un modello semplice (si spera) e che ha una distribuzione uniforme tra l'insieme di numeri restituiti.

Un test corretto per un PRNG implicherà l'esecuzione di almeno 100 volte e quindi controllerà la distribuzione dell'output (che è una risposta diretta alla seconda parte della domanda).

Una risposta alla prima domanda è quasi la stessa: esegui il test circa 100 volte con {1, 2, ..., n} e conta il numero di volte in cui ogni elemento è stato in ogni posizione. Dovrebbero essere tutti approssimativamente uguali se il metodo shuffle è buono.

Una questione completamente diversa è come testare i PRNG di livello crittografico. Questa è una questione in cui probabilmente non dovresti soffermarti, a meno che tu non sappia davvero cosa stai facendo. Le persone sono state conosciute per distruggere (leggi: aprire buchi catastrofici in) buoni cryptosystems con solo poche "ottimizzazioni" o modifiche banali .

EDIT: ho completamente riletto la domanda, la risposta migliore e la mia. Mentre i punti che sto facendo valgono ancora, vorrei la risposta di Bill The Lizard. I test unitari sono di natura booleana - o falliscono, o hanno successo, e sono quindi inadatti per testare "quanto sono buone" le proprietà di un PRNG (o un metodo che usa un PRNG), poiché qualsiasi risposta a questa domanda sarebbe quantitativa , piuttosto che polare.

Ci sono due parti a questo: testare la randomizzazione e testare le cose che usano la randomizzazione.

Il test della randomizzazione è relativamente semplice. Controllate che il periodo del generatore di numeri casuali sia come vi aspettate (per alcuni campioni usando alcuni semi kinda-random, entro una certa soglia) e che la distribuzione dell'output su una grande dimensione del campione è come ci si aspetta deve essere (entro una certa soglia).

Testare le cose che usano la randomizzazione è meglio farlo con un generatore di numeri psuedo-casuali deterministico. Poiché l'output della randomizzazione è noto in base al seme (i suoi input), è possibile eseguire il test dell'unità come normale in base agli input rispetto agli output previsti. Se il tuo RNG è non deterministico, allora prendilo in giro con uno che è deterministico (o semplicemente non casuale). Prova la randomizzazione in isolamento dal codice che la consuma.

Lascia che funzioni un po 'di volte e visualizza i tuoi dati .

Ecco un esempio di shuffle di Coding Horror , tu può vedere che l'algoritmo è OK o no:

È facile vedere che ogni elemento possibile viene restituito almeno una volta (i limiti sono OK) e che la distribuzione è OK.

Puntatori generali che ho trovato utili quando si tratta di codice che richiede input casuali: Controllare i casi limite di casualità prevista (valori max e min e i valori max + 1 e min-1, se applicabili). Controlla i luoghi (sopra, sopra e sotto) dove i numeri hanno punti di inflessione (cioè -1, 0, 1 o maggiore di 1, meno di 1 e non negativo per i casi in cui un valore frazionale potrebbe compromettere la funzione). Controlla alcuni posti completamente al di fuori dell'input consentito. Controlla alcuni casi tipici. Puoi anche aggiungere un input casuale, ma per un test unitario che ha l'indesiderato effetto collaterale che lo stesso valore non è sotto test ogni volta che viene eseguito il test (un approccio seed può funzionare, prova i primi 1.000 numeri casuali da seme S or somesuch).

Per testare l'output di una funzione casuale, è importante identificare l'obiettivo. Nel caso delle carte, l'obiettivo è di testare l'uniformità del generatore casuale 0-1, per determinare se tutte le 52 carte appaiono nel risultato, o qualche altro obiettivo (forse tutto questo elenco e altro)?

Nell'esempio specifico, devi assumere che il tuo generatore di numeri casuali sia opaco (proprio come non ha senso testare l'unità syscall o malloc- a meno che tu scriva sistemi operativi). Può essere utile misurare il generatore di numeri casuali, ma il tuo obiettivo non è scrivere un generatore casuale, solo per vedere che ottieni 52 carte ogni volta e che cambiano ordine.

Questo è un modo molto lungo per dire che ci sono davvero due compiti di test qui: testare che l'RNG sta producendo la giusta distribuzione e controllare che il codice shuffle della carta stia usando quel RNG per produrre risultati randomizzati. Se stai scrivendo il RNG, usa l'analisi statistica per dimostrare la tua distribuzione, se stai scrivendo il mescolatore di carte, assicurati che ci siano 52 carte non ripetute in ogni uscita (è un caso migliore per il test di ispezione che stai usando il RNG).

Puoi contare su generatori di numeri casuali sicuri

Ho appena avuto un pensiero orribile: non stai scrivendo il tuo generatore di numeri casuali vero?

Supponendo che non lo sia, dovresti testare il codice di cui sei responsabile , non il codice di altre persone (come l'implementazione SecureRandom per il tuo framework).

Verifica del codice

Per verificare che il tuo codice risponda correttamente, è normale utilizzare un metodo a bassa visibilità per produrre numeri casuali in modo che possa essere facilmente sostituito da una classe di test unitario. Questo metodo sovrascritto elimina efficacemente il generatore di numeri casuali e ti dà il controllo completo su ciò che viene prodotto e quando. Di conseguenza puoi esercitare completamente il tuo codice, che è l'obiettivo del test unitario.

Ovviamente controllerai le condizioni del bordo e assicurerai che lo shuffling avvenga esattamente come gli algoritmi dettano gli input appropriati.

Test del generatore di numeri casuali sicuro

Se non si è sicuri che il generatore di numeri casuali sicuro per la propria lingua non sia realmente casuale o buggato (fornisce valori fuori intervallo, ecc.), è necessario eseguire un'analisi statistica dettagliata dell'output su diverse centinaia di milioni di iterazioni. Traccia la frequenza di occorrenza di ciascun numero e dovrebbe presentarsi con uguale probabilità. Se i risultati sono errati in un modo o nell'altro, è necessario riportare i risultati ai progettisti del framework. Saranno sicuramente interessati a risolvere il problema poiché i generatori di numeri casuali sicuri sono fondamentali per molti algoritmi di crittografia.

Bene, non sarai mai sicuro al 100%, quindi il meglio che puoi fare è che è probabile che i numeri siano casuali. Scegli una probabilità: dì che un campione di numeri o elementi verrà visualizzato x volte dato un milione di campioni, entro un margine di errore. Esegui la cosa un milione di volte e verifica se è all'interno del margine. Fortunatamente, i computer rendono questo genere di cose facili da fare.

Per verificare che una fonte di numeri casuali stia generando qualcosa che abbia almeno l'apparenza di casualità, avrei il test generare una sequenza abbastanza grande di byte, scriverli in un file temporaneo, e quindi eseguire lo shell out strumento ent di Fourmilab. Fornisci l'opzione -t (terse) in modo da generare un CSV facile da analizzare. Quindi controlla i vari numeri per vedere che sono "buoni".

Per decidere quali numeri sono buoni, utilizza una fonte nota di casualità per calibrare il test. Il test dovrebbe quasi sempre passare quando viene fornito un buon insieme di numeri casuali. Perché anche una sequenza veramente casuale ha una probabilità di generare una sequenza che sembra non casuale, non è possibile ottenere un test che è certo di passare. È sufficiente selezionare soglie che rendono improbabile che una sequenza casuale causerà un errore di test. Non è divertente la casualità?

Nota: non è possibile scrivere un test che mostri che un PRNG genera una sequenza "casuale". Puoi solo scrivere un test che, se passa, indica una certa probabilità che la sequenza generata dal PRNG sia "casuale". Benvenuto nella gioia della casualità!

Caso 1: test di un shuffle:

Considera una matrice [0, 1, 2, 3, 4, 5], mischialo, cosa può andare storto? Le solite cose: a) niente shuffle, b) mischiare 1-5 ma non 0, mischiare 0-4 ma non 5, mescolare e generare sempre lo stesso modello, ...

Un test per catturarli tutti:

Mescola 100 volte, aggiungi i valori in ogni slot. La somma di ogni slot dovrebbe essere simile all'altro. Avg / Stddev può essere calcolato. (5 + 0) /2=2.5, 100 * 2.5 = 25. Il valore previsto è di circa 25, per esempio.

Se i valori sono fuori portata, c'è una piccola possibilità che tu abbia un falso negativo. Puoi calcolare quanto è grande questa possibilità. Ripeti il test. Bene - certo c'è una piccola possibilità, che il test fallisca 2 volte di seguito. Ma non hai una routine che cancella automaticamente la tua fonte, se il test unitario fallisce, vero? Eseguilo di nuovo!

Può fallire 3 volte di seguito? Forse dovresti tentare la fortuna alla lotteria.

Caso 2: tira un dado

La domanda dei dadi è la stessa domanda. Lancia i dadi 6000 volte.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;