Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Efficienza della funzione rand()
Forum - C/C++ - Efficienza della funzione rand()

Avatar
xeeynamo (Normal User)
Pro


Messaggi: 66
Iscritto: 14/03/2008

Segnala al moderatore
Postato alle 14:45
Giovedì, 09/07/2009
Salve a tutti!
Mi servirebbe per un progettino personale realizzare un ciclo che riempa totalmente un vettore bidimensionale. L'algoritmo per me non è  un problema, di fatti in 2 o 3 minuti ho completato l'algoritmo principale senza problemi, però c'è un problema enorme che mi costringe ad arrestare questo piccolo progetto: la funzione rand() non è efficiente al 100%... Di fatti con un vettore bidimensionale 80x24 (1920 celle), ne riesce a riempire solamente 808, meno della metà...
Questo è l'algoritmo che ho sviluppato:
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <windows.h>
  4.  
  5. int Rand(int r){
  6.    int i=rand();
  7.    for(;i>r;i-=r);
  8.    return i;
  9. }
  10. void SetXY(byte x, byte y){
  11.     COORD coord={x,y};
  12.     SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
  13. }
  14. #define SX 80
  15. #define SY 24
  16.  
  17. int main(){
  18.     bool v[SX][SY];
  19.     int x,y;
  20.     while(1){
  21.         x=Rand(SX);
  22.         y=Rand(SY);
  23.         if (!v[x][y]){
  24.             SetXY(x,y); printf("X");
  25.             v[x][y]=1;
  26.         }
  27.     }
  28. }


PM Quote
Avatar
theprogrammer (Normal User)
Guru^2


Messaggi: 2509
Iscritto: 28/01/2009

Segnala al moderatore
Postato alle 14:56
Giovedì, 09/07/2009
Testo quotato

Postato originariamente da xeeynamo:

la funzione rand() non è efficiente al 100%...



Che vuol dire? In che senso non e' "efficiente"? Non vedo come possa essere misurata l'efficienza della rand ...

Testo quotato

Di fatti con un vettore bidimensionale 80x24 (1920 celle), ne riesce a riempire solamente 808, meno della metà...



Ancora ... cosa vuoi dire? Sicuramente non hai adottato un corretto algoritmo ...


- Se le mie risposte non vi soddisfano, ignoratele, altrimenti un "grazie" e' molto gradito ...

"Dai un pesce (programma) a un uomo e lo nutrirai per un giorno. Insegnagli a pescare (programmare) e lo nutrirai per tutta la vita." (niente pappa pronta)
PM Quote
Avatar
xeeynamo (Normal User)
Pro


Messaggi: 66
Iscritto: 14/03/2008

Segnala al moderatore
Postato alle 18:16
Giovedì, 09/07/2009
Testo quotato

Postato originariamente da theprogrammer:

Testo quotato

Postato originariamente da xeeynamo:

la funzione rand() non è efficiente al 100%...



Che vuol dire? In che senso non e' "efficiente"? Non vedo come possa essere misurata l'efficienza della rand ...

Testo quotato

Di fatti con un vettore bidimensionale 80x24 (1920 celle), ne riesce a riempire solamente 808, meno della metà...



Ancora ... cosa vuoi dire? Sicuramente non hai adottato un corretto algoritmo ...



Efficiente nel senso che se voglio che si presenti un numero da 0 a 9999, è vero che la funzione rand mi restituisce dei numeri in quel range, ma non mi permette di riuscire a darmi tutti e i 10000 numeri ma solo ad esempio 2000... Nel caso del mio programma, vengono inizializzate 1920 celle col valore 0, e che devono essere riempite una ad una casualmente col valore 1, solo che siccome il rand non riesce a farmi uscire determinati numeri allora non tutte le celle vengono riempite, ma solo 808. E penso che il mio algoritmo è perfetto :)

PM Quote
Avatar
theprogrammer (Normal User)
Guru^2


Messaggi: 2509
Iscritto: 28/01/2009

Segnala al moderatore
Postato alle 18:56
Giovedì, 09/07/2009
1) devi usare la srand, una volta, per inizializzare il generatore di numeri casuali

2) puoi generare il valore casuale con una semplice formula, evitando la for che rallenta tutto ...

e soprattutto

3) devi azzerare l'array prima di usarlo, perche' i valori all'inizio del programma sono casuali ... lo puoi fare usando la funzione memset

In pratica, il programma diventa

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <windows.h>
  4. #include <time.h>
  5.  
  6. void SetXY(byte x, byte y)
  7. {
  8.     COORD coord={x,y};
  9.     SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
  10. }
  11.  
  12. #define SX 80
  13. #define SY 24
  14.  
  15. int main()
  16. {
  17.     bool v[SX][SY];
  18.     int x,y;
  19.  
  20.     memset(v, 0, sizeof(bool)*SX*SY);
  21.     srand (time(NULL));
  22.  
  23.     while(1)
  24.     {
  25.         x=rand() % SX;
  26.         y=rand() % SY;
  27.        
  28.         if (!v[x][y])
  29.         {
  30.             SetXY(x,y); printf("X");
  31.             v[x][y]=1;
  32.         }
  33.     }
  34. }


Ultima modifica effettuata da theprogrammer il 09/07/2009 alle 18:59


- Se le mie risposte non vi soddisfano, ignoratele, altrimenti un "grazie" e' molto gradito ...

"Dai un pesce (programma) a un uomo e lo nutrirai per un giorno. Insegnagli a pescare (programmare) e lo nutrirai per tutta la vita." (niente pappa pronta)
PM Quote
Avatar
xeeynamo (Normal User)
Pro


Messaggi: 66
Iscritto: 14/03/2008

Segnala al moderatore
Postato alle 19:11
Giovedì, 09/07/2009
wow, funziona in maniera perfetta O_O. Il problema a quanto pare stava nell'azzerare la variabile v. Poi anche togliendo l'srand, il tutto funziona con success. Comunque grazie :k:

PM Quote
Avatar
theprogrammer (Normal User)
Guru^2


Messaggi: 2509
Iscritto: 28/01/2009

Segnala al moderatore
Postato alle 19:13
Giovedì, 09/07/2009
Non devi togliere la srand ... altrimenti avrai la stessa sequenza casuale ad ogni avvio.

Leggiamola la documentazione ...


- Se le mie risposte non vi soddisfano, ignoratele, altrimenti un "grazie" e' molto gradito ...

"Dai un pesce (programma) a un uomo e lo nutrirai per un giorno. Insegnagli a pescare (programmare) e lo nutrirai per tutta la vita." (niente pappa pronta)
PM Quote
Avatar
Xaratroom (Ex-Member)
Expert


Messaggi: 526
Iscritto: 03/04/2008

Segnala al moderatore
Postato alle 19:34
Giovedì, 09/07/2009
Testo quotato

Postato originariamente da xeeynamo:
Efficiente nel senso che se voglio che si presenti un numero da 0 a 9999, è vero che la funzione rand mi restituisce dei numeri in quel range, ma non mi permette di riuscire a darmi tutti e i 10000 numeri ma solo ad esempio 2000... Nel caso del mio programma, vengono inizializzate 1920 celle col valore 0, e che devono essere riempite una ad una casualmente col valore 1, solo che siccome il rand non riesce a farmi uscire determinati numeri allora non tutte le celle vengono riempite, ma solo 808. E penso che il mio algoritmo è perfetto :)


Questa tua risposta mi ha fatto venire un dubbio, perchè, in realtà, la rand() permette di generare solo numeri pseudocasuali...
Mi sono chiesto: se genero un numero di valori molto grande, come si comporta ? Riuscirà a generare tutti i valori del range per un numero di prove molto grande ?
Ho, quindi, fatto un programmino, per controllare se salta qualche valore del range:
Codice sorgente - presumibilmente C++

  1. /*
  2.  * Test per rand ()
  3.  */
  4. #include <iostream>
  5. #include <string>
  6. #include <ctime>
  7. #include <cstdlib>
  8. #include <set>
  9. using namespace std;
  10.  
  11. unsigned int leggiValoreNumerico (string messaggio) {
  12.         /*Stamèpa messaggio sullo standard output e ritorna un valore unsigned letto da tastiera*/
  13.         unsigned int temp;
  14.         cout << messaggio;
  15.         cin >> temp;
  16.         return temp;
  17. }
  18.  
  19. main (int argc, char *argv[]) {
  20.         srand(time(NULL)); //creo un seme ottenendo il timestamp della data e ora attuale
  21.        
  22.         unsigned int range = leggiValoreNumerico ("Inserire il valore massimo da generare: ");
  23.         unsigned int prove = leggiValoreNumerico ("Inserire il numero di prove: ");
  24.  
  25.         multiset<unsigned int> valoriGenerati; //creo un insieme contenente valori generati e occorrenze
  26.        
  27.         for (unsigned int i = 0; i < range*prove; i++)
  28.                 valoriGenerati.insert (rand()%range); //riempio l'insieme
  29.  
  30.         cout << "<valore>, <numero occorrenze>" << endl;
  31.         for (unsigned int i = 0; i < range; i++)
  32.                 cout << i << ", " << (unsigned int) valoriGenerati.count (i) << endl;
  33.  
  34.         return 0;
  35. }


Il programma è semplice: dato un range e un numero di prove, genera range*numero di prove numeri casuali e li inserisce in un multiset. Al termine stampa l'occorrenze dei valori nel range (in formato csv).

Ho importato il csv su calc e ho calcolato la media ponderata dei valori, nonchè un grafico:

Con range 100, numero di prove 30 (per un totale complessivo di 300 generazioni) ho ottenuto media 50,18.
Allego il grafico.

I risultati credo che parlino da soli (non ho provveduto a fare calcoli extra o a scomodare la gaussiana perchè è palese che il funzionamento della rand è accettabile).


Xaratroom ha allegato un file: grafico.jpg (117612 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Xaratroom il 09/07/2009 alle 19:35


bool Woman::makeYourselfBetter() {
       goto bathroom;

bathroom:
       while (1);

       return this->_isGoodResult();
}
PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 2:16
Sabato, 11/07/2009
mmmh....

leggendo questa discussione mi è venuta in mente una vecchissima questione riguardo la generazione dei numeri pseudo-casuali....

Ammettiamo di voler generare i numeri compresi nel range 0-99.

La soluzione spontanea al problema sarebbe rand() % 100. Cioè, prendo un numero casuale, lo divido per 100, prendo il resto e sicuramente il risultato sarà compreso tra 0 e 99...

Concettualmente non fa una grinza, ma c'è una cosa che non funziona.
I numeri generati da rand() sono interi a 32 bit (dipende dalla macchina ovviamente). Questo significa che il range "nativo" della funzione è da 0 a 4294967295 (2^32 - 1, con l'aiuto della calcolatrice).
Se dividessimo per 100 tutti i numeri del range, e considerassimo i resti, vedremmo che (alla fine del conto) ci fermeremmo al numero 95. Quindi in totale, mancheranno all'appello un 96, un 97, un 98 e un 99 per pareggiare i conti. In termini matematici, le classi modulo [96], [97], [98] e [99] hanno un elemento in meno rispetto alle precedenti 96 classi (dalla classe [0] alla classe [95]). Quindi tirando a sorte, i numeri 96,97,98 e 99 avrebbero meno probabilità di essere pescati rispetto agli altri.

Ecco perchè in campo finanziario (quando si devono generare numeri casuali per chiavi crittografiche nelle transazioni bancarie) si usano metodi più precisi per generare numeri casuali.

Un metodo migliore è quello di generare un numero a 32 bit, elevarlo al quadrato (diventando così di 64 bit), scartare i primi 16 bit e gli ultimi 16 bit prendendo così in considerazione i soli 32 bit centrali, e usando questi ultimi per generare i numeri che ci interessano.

Questo metodo funziona perchè, e potete verificarlo con carta e penna, le cifre centrali di una moltiplicazione (in questo caso moltiplicazione per se stesso), sono quelle che vengono influenzate sia dalle cifre a destra che dalle cifre a sinistra degli operandi, eliminando il problema della "scarsità" degli elementi 96, 97, 98 e 99.

Ovviamente il ragionamento è applicabile a qualunque range generico. Fanno eccezione i range potenze di 2, perchè in questo caso si tratta di sottomultipli esatti del range nativo e quindi non esistono disparità tra le classi modulari (cioè i gruppi di numeri) che ci interessano.

(stasera mi sento in vena di filosofeggiare... hihihi) :)


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote