Test per valore casuale - Pensieri su questo approccio?

StackOverflow https://stackoverflow.com/questions/122741

Domanda

OK, ho lavorato su un selettore di immagini casuale e un sistema di code (quindi non vedi le stesse immagini troppo spesso).

Tutto stava andando a gonfie vele (per quanto riguarda il mio codice schifoso) fino a quando sono arrivato al punto casuale. Volevo provarlo, ma come lo provi? Non esiste Debug.Assert (i.IsRandom) (purtroppo): D

Quindi, ho avuto il cervello su di esso dopo averlo innaffiato con un po 'di tè e mi è venuto in mente il seguente, mi chiedevo solo se potevo avere i tuoi pensieri?

  • In pratica sapevo che il problema era il casuale , quindi l'ho strappato a un delegato (che sarebbe poi passato al costruttore di oggetti).
  • Ho quindi creato una classe che praticamente esegue la stessa logica del codice live , ma ricorda il valore selezionato in una variabile privata.
  • Ho quindi lanciato quel delegato alla classe dal vivo e ho provato contro questo:

cioè. 

Debug.Assert(myObj.RndVal == RndIntTester.ValuePassed);

Ma non ho potuto fare a meno di pensare, stavo sprecando il mio tempo? Ho passato tutto questo attraverso molte iterazioni per vedere se è caduto in qualsiasi momento ecc.

Pensi che stavo perdendo tempo con questo? O avrei potuto cavarmela con:

Impressionante generatore di numeri casuali

Risposta di GateKiller mi ha ricordato questo:

Dilbert Random

Aggiornamento per chiarire

  • Dovrei aggiungere che praticamente non voglio mai vedere lo stesso risultato più di X numero di volte da un pool di dimensioni Y.
  • L'aggiunta del contenitore di prova mi ha sostanzialmente permesso di vedere se una qualsiasi delle immagini precedentemente selezionate era "a caso" selezionato.
  • Immagino che tecnicamente la cosa qui testata non sia nell'RNG (dal momento che non ho mai scritto quel codice) ma il fatto che mi aspetto casuale risultati da un pool limitato e voglio seguirli .
È stato utile?

Soluzione

Prova dal requisito: " in modo da non vedere le stesse immagini troppo spesso "

Richiedi 100 immagini. Hai visto un'immagine troppo spesso?

Altri suggerimenti

C'è un utile elenco di casualità statistica e test ricerca correlata su Wikipedia. Nota che non saprai per certo che una fonte è veramente casuale con la maggior parte di questi, avrai semplicemente escluso alcuni modi in cui potrebbe essere facilmente prevedibile.

Se hai un set fisso di elementi e non vuoi che si ripetano troppo spesso, mescola la raccolta in modo casuale. Quindi sarai sicuro di non vedere mai la stessa immagine due volte di seguito, di sentire l'ascolto della radio Top 20, ecc. Farai un passaggio completo attraverso la raccolta prima di ripetere. 

Item[] foo = …
for (int idx = foo.size(); idx > 1; --idx) {
  /* Pick random number from half-open interval [0, idx) */
  int rnd = random(idx); 
  Item tmp = foo[idx - 1];
  foo[idx - 1] = foo[rnd];
  foo[rnd] = tmp;
}

Se hai troppi oggetti da raccogliere e mescolare tutti in una volta (10s di migliaia di immagini in un repository), puoi aggiungere un po 'di divisione e conquista allo stesso approccio. Mescola gruppi di immagini, quindi mescola ogni gruppo.

Un approccio leggermente diverso che potrebbe valere per la tua dichiarazione di problema rivista è di avere il tuo "selettore di immagini" l'implementazione mantiene la cronologia delle selezioni recenti in una coda al massimo Y . Prima di restituire un'immagine, verifica se è già nella coda X e, in tal caso, ne seleziona un'altra a caso, fino a quando non ne trova una che passa.

Se stai davvero chiedendo di testare la qualità del generatore di numeri casuali, dovrò aprire il libro delle statistiche.

È impossibile verificare se un valore è veramente casuale o no. Il meglio che puoi fare è eseguire il test un numero elevato di volte e verificare che tu abbia ottenuto una distribuzione appropriata, ma se i risultati sono veramente casuali, anche questo ha una (molto piccola) possibilità di fallire.

Se stai facendo dei test su white box e conosci il tuo seme casuale, allora puoi effettivamente calcolare il risultato atteso, ma potresti aver bisogno di un test separato per testare la casualità del tuo RNG.

  

La generazione di numeri casuali è   troppo importante per essere lasciato al caso. - Robert R. Coveyou

Per risolvere il problema psicologico:

Un modo decente per prevenire apparenti ripetizioni è selezionare alcuni elementi a caso dall'insieme completo, scartando i duplicati. Gioca a quelli, quindi selezionane altri. Quanti sono " pochi " dipende dalla velocità con cui li stai giocando e da quanto è grande il set completo, ma ad esempio evitando una ripetizione all'interno del più grande di "20", e "5 minuti". potrebbe essere OK. Fai test utente: in quanto programmatore sarai così stanco delle presentazioni che non sei un buon soggetto di prova.

Per testare il codice randomizzato, direi:

Passaggio 1: specifica in che modo il codice DEVE mappare i numeri casuali grezzi alle scelte nel tuo dominio e assicurati che il codice utilizzi correttamente l'output del generatore di numeri casuali. Prova questo deridendo il generatore (o seminandolo con un valore di test noto se si tratta di un PRNG).

Passaggio 2: assicurati che il generatore sia sufficientemente casuale per i tuoi scopi. Se hai utilizzato una funzione di libreria, puoi farlo leggendo la documentazione. Se hai scritto il tuo, perché?

Passaggio 3 (solo statistici avanzati): eseguire alcuni test statistici per la casualità sull'output del generatore. Assicurati di sapere qual è la probabilità di un falso fallimento nel test.

Ci sono libri interi che si possono scrivere sulla casualità e valutare se qualcosa appare come casuale, ma ti salverò le pagine di matematica. In breve, puoi utilizzare un test chi-square come modo per determinare quanto bene un apparentemente "casuale" la distribuzione si adatta alle tue aspettative.

Se stai usando Perl, puoi usare Statistics :: ChiSquare modulo per fare il duro lavoro per te.

Tuttavia, se vuoi assicurarti che le tue immagini siano uniformemente distribuite , probabilmente non vorrai che siano veramente casuali. Invece, ti suggerirei di prendere l'intero elenco di immagini, di mescolare quell'elenco e di rimuovere un elemento da esso ogni volta che hai bisogno di un "casuale" Immagine. Quando l'elenco è vuoto, lo ricostruisci, ri-mescoli e ripeti.

Questa tecnica significa che, dato un insieme di immagini, ogni singola immagine non può apparire più di una volta ogni iterazione attraverso il tuo elenco. Le tue immagini non possono fare a meno di essere distribuite uniformemente.

Tutto il meglio,

Paul

Ciò che il Casuale e funzioni simili ti danno sono solo numeri pseudo-casuali, una serie di numeri prodotti attraverso una funzione. Di solito, dai a quella funzione il suo primo parametro di input (a.k.a. il "seed") che viene usato per produrre il primo "random" numero. Successivamente, l'ultimo valore viene utilizzato come parametro di input per la successiva iterazione del ciclo. Puoi controllare l'articolo di Wikipedia su "generatore di numeri pseudocasuali", la spiegazione è molto buona.

Tutti questi algoritmi hanno qualcosa in comune: la serie si ripete dopo una serie di iterazioni . Ricorda, questi non sono numeri veramente casuali, solo serie di numeri che sembrano casuali. Per selezionare un generatore piuttosto che un altro, devi chiederti: per cosa lo vuoi?

Come testate la casualità? In effetti puoi. Ci sono molti test per questo. Il primo e più semplice è, ovviamente, far funzionare il tuo generatore di numeri pseudo-casuale un numero enorme di volte e compilare il numero di volte in cui appare ogni risultato. Alla fine, ogni risultato avrebbe dovuto apparire un numero di volte molto vicino a (numero di iterazioni) / (numero di risultati possibili). Maggiore è la deviazione standard di questo, peggiore è il tuo generatore.

Il secondo è: quanti numeri casuali stai usando in quel momento? 2, 3? Prendili in coppia (o tripplet) e ripeti l'esperimento precedente: dopo un numero molto lungo di iterazioni, ogni risultato atteso dovrebbe apparire almeno una volta, e di nuovo il numero di volte in cui ogni risultato è apparso non dovrebbe essere troppo lontano da l'atteso. Ci sono alcuni generatori che funzionano bene per prendere uno o 2 alla volta, ma falliscono in modo spettacolare quando ne prendi 3 o più (RANDU qualcuno?).

Esistono altri test più complessi: alcuni implicano la stampa dei risultati in scala logaritmica o su un piano con un cerchio nel mezzo e quindi il conteggio di quanti diagrammi cadono all'interno, altri ... Credo che quelli 2 sopra dovrebbe bastare la maggior parte delle volte (a meno che tu non sia un matematico schizzinoso).

Casuale è Casuale. Anche se la stessa immagine appare 4 volte di seguito, potrebbe comunque essere considerata casuale.

La mia opinione è che qualcosa di casuale non può essere testato correttamente.

Sicuramente puoi provare a provarlo, ma ci sono così tante combinazioni per provare che stai meglio affidandoti al RNG e controllando in loco una grande manciata di casi.

Bene, il problema è che i numeri casuali per definizione possono ripetersi (perché sono ... aspettatelo: casuale). Forse quello che vuoi fare è salvare l'ultimo numero casuale e confrontare quello calcolato con quello, e se uguale calcola solo un altro ... ma ora i tuoi numeri sono meno casuali (so che non esiste un cosa come "più o meno" casualità, ma fammi usare il termine proprio questa volta), perché sono garantiti per non ripetere.

Ad ogni modo, non dovresti mai pensare così tanto a numeri casuali. :)

Come altri hanno sottolineato, è impossibile testare davvero la casualità. Puoi (e dovresti) avere la casualità contenuta in un particolare metodo, quindi scrivere unit test per ogni altro metodo. In questo modo, puoi testare tutte le altre funzionalità, supponendo che tu possa ottenere un numero casuale da quest'ultima parte.

archivia i valori casuali e prima di utilizzare il prossimo numero casuale generato, controlla il valore memorizzato.

Qualsiasi buon generatore di numeri pseudo-casuali ti permetterà di seminare il generatore. Se esegui il seeding del generatore con lo stesso numero, il flusso di numeri casuali generati sarà lo stesso. Quindi perché non seminare il generatore di numeri casuali e quindi creare i test unitari in base a quel particolare flusso di numeri?

Per ottenere una serie di numeri casuali non ripetitivi:

  1. Crea un elenco di numeri casuali.
  2. Aggiungi un numero progressivo a ciascun numero casuale
  3. Ordina l'elenco in sequenza in base al numero casuale originale
  4. Usa il tuo numero progressivo come nuovo numero casuale.

Non testare la casualità, prova per vedere se i risultati che stai ottenendo sono desiderabili (o, piuttosto, prova a ottenere risultati indesiderati alcune volte prima di accettare che i tuoi risultati saranno probabilmente desiderabili). Sarà impossibile garantire che non si ottenga mai un risultato indesiderato se si sta testando un output casuale, ma è possibile almeno aumentare le possibilità che si noti che accada.

Vorrei prendere N pool di dimensioni Y, verificando la presenza di risultati che compaiono più di X numero di volte, oppure prendere un pool di dimensioni N * Y, controllando ogni gruppo di dimensioni Y per qualsiasi risultato che appare più di X volte (da 1 a Y, da 2 a Y + 1, da 3 a Y + 2, ecc.). Ciò che N dipende da quanto affidabile vuoi che sia il test.

I numeri casuali sono generati da una distribuzione. In questo caso, ogni valore dovrebbe avere la stessa propensione di apparire. Se si calcola una quantità infinita di random, si ottiene la distribuzione esatta.

In pratica, chiama la funzione più volte e controlla i risultati. Se si prevede di avere N immagini, calcolare 100 * N randoms, quindi contare quanti di ciascun numero previsto sono stati trovati. La maggior parte dovrebbe apparire 70-130 volte. Rieseguire il test con diversi semi casuali per vedere se i risultati sono diversi.

Se trovi che il generatore che usi ora non è abbastanza buono, puoi facilmente trovare qualcosa. Google per " Mersenne Twister " - è molto più casuale di quanto tu abbia mai bisogno.

Per evitare la riapparizione delle immagini, è necessario qualcosa di meno casuale. Un approccio semplice sarebbe quello di verificare i valori non consentiti, se è uno di questi, ricalcolare.

Sebbene non sia possibile verificare la casualità, è possibile verificare la correlazione o la distribuzione di una sequenza di numeri.

Obiettivo difficile da testare: ogni volta che abbiamo bisogno di un'immagine, seleziona 1 di 4 immagini a caso.

Obiettivo facile da testare: per ogni 100 immagini selezionate, ciascuna delle 4 immagini deve apparire almeno 20 volte.

Sono d'accordo con Adam Rosenfield. Per la situazione di cui stai parlando, l'unica cosa che puoi utilmente testare è la distribuzione nell'intervallo.

La situazione che di solito incontro è che sto generando numeri pseudocasuali con il PRNG della mia lingua preferita e poi li sto manipolando nell'intervallo desiderato. Per verificare se le mie manipolazioni hanno influenzato la distribuzione, ho generato un mucchio di numeri, li manipolo e quindi controllo la distribuzione dei risultati.

Per ottenere un buon test, dovresti generare almeno un paio di ordini di grandezza in più di quanti ne contenga l'intervallo. Più valori usi, migliore è il test. Ovviamente se hai un intervallo molto ampio, questo non funzionerà poiché dovrai generare troppi numeri. Ma nella tua situazione dovrebbe funzionare bene.

Ecco un esempio in Perl che illustra cosa intendo: 

for (my $i=0; $i<=100000; $i++) {
   my $r = rand;        # Get the random number
   $r = int($r * 1000); # Move it into the desired range
   $dist{$r} ++;        # Count the occurrences of each number
}

print "Min occurrences: ", (sort { $a <=> $b } values %dist)[1], "\n";
print "Max occurrences: ", (sort { $b <=> $a } values %dist)[1], "\n";

Se lo spread tra le occorrenze minima e massima è ridotto, la distribuzione è buona. Se è ampia, la tua distribuzione potrebbe essere negativa. Puoi anche utilizzare questo approccio per verificare se il tuo intervallo è stato coperto e se mancavano dei valori.

Ancora una volta, più numeri vengono generati, più validi saranno i risultati. Tendo a iniziare in piccolo e lavorare fino a tutto ciò che la mia macchina gestirà in un ragionevole lasso di tempo, ad es. cinque minuti.

Supponendo che tu stia testando un intervallo per casualità all'interno di numeri interi, un modo per verificarlo è quello di creare un gajillion (beh, forse circa 10.000) numeri "casuali" e tracciare la loro occorrenza su un istogramma. 

          ******    ******           ****
***********************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Quanto sopra mostra una distribuzione 'relativamente' normale.

se sembrava più distorto, come questo: 

          ******    ******           ****
    ************  ************  ************
    ************  ************  ***************
    ************  ************  ****************
    ************  ************  *****************
    ************  ************  *****************
   ***************************  ******************
   **************************** ******************
******************************* ******************
**************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Quindi puoi vedere che c'è meno casualità. Come altri hanno già detto, c'è anche il problema della ripetizione da affrontare.

Se dovessi scrivere un file binario di 10.000 numeri casuali dal tuo generatore usando, pronuncia un numero casuale da 1 a 1024 e prova a comprimere quel file usando un po 'di compressione (zip, gzip, ecc.) allora potresti confrontare le due dimensioni del file. Se c'è "molta" compressione, non è particolarmente casuale. Se non ci sono molti cambiamenti nelle dimensioni, allora è "abbastanza casuale".

Perché funziona

Gli algoritmi di compressione cercano schemi (ripetizione e altro) e li riducono in qualche modo. Un modo per visualizzare questi algoritmi di compressione è una misura della quantità di informazioni in un file. Un file altamente compresso ha poche informazioni (ad esempio casualità) e un file poco compresso ha molte informazioni (casualità)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top