Articole
Communitate afiliata
Monitorizare trafic
|
Generatoarele de numere aleatoare din TR1 Mediu: VS 2008; VC++ 2008 Feature Pack |
|
TR1 aduce un nou header bibliotecii standard, numit <random< care defineste cateva generatoare de numere. Pana la TR1 singurul mod de a genera numere aleatoare in C++ era folosirea functiei rand(). Aceasta, desi trivial de folosit si buna pentru majoritatea aplicatiilor nu e suficient de performanta pentru unele categorii de aplicatii. In acest caz dezvoltatorii apelau la alte implementari cu ar fi Marsenne Twister. TR1 aduce in C++ cateva astfel de generatoare, inclusiv twisterul Marsenne. Din pacate documentatia pentru aceste generatoare este destul de simplista, iar exemplele in MSDN lipsesc cu desavarsire. Voi incerca in acest articol sa clarific modul de folosire al acestor generatoare. Ce este un generator?Un generator de numere aleatoare, contrar poate unei prime impresii, nu genereaza numere aleatoare ci "pseudo" aleatoare, numere care doar dau impresia ca sunt aleatoare. Generarea de numere inseamna executia unui algoritm, fiecare nou numar, depinzand intr-un fel sau altul de ultimul generat. Din aceasta cauza, orice astfel de algoritm are nevoia de un numar initial, numit "seed". Un algoritm care e initializat cu acelasi seed va genera aceiasi secventa de numere. Acesta este un aspect important, intrucat in practica se uita adesea sa se initializeze generatorul. Fiind un algoritm matematic bine determinat, si numerele generate sunt deterministe. Doar un generator hardware poate produce numere cu adevarat aleatoare. Inainte de TR1Asa cum spuneam anterior, pana la TR1 singura modalitate "standard" de a genera numere aleatoare, era folosind functia rand(). Exemplul de mai jos exemplifica folosirea ei pentru a genera numere in intervalul [0, 10).
int main()
{
srand((unsigned int)time(NULL));
for(int i = 0; i < 10; ++i)
{
std::cout << rand()%10 << " ";
}
std::cout << std::endl;
return 0;
}
Dupa cum se observa prima data am initializat generatorul cu o valoare initiala, care este valoarea returnata de functia time(); cu alte cuvinte, numarul de secunde scurse de la 1 Ianuarie 1970. In lipsa acestei initializari, toate secventele generate vor fi identice. Atentie, in cazul acestui mod de initializare, daca se fac doua apeluri la srand() in mai putin de 1 secunda, atunci algoritmul va fi initializat cu aceiasi valoarea, si secventele generate for fi identice. Noutatile din TR1TR1 aduce nou trei categorii de entitati: generatoare, motoare (engine) si distributii. Un generator este un obiect care produce numere pseudo-aleatoare. Un generator care produce numere uniform distribuite intr-un interval se numeste (motor). Motoarele si distributiile se pot combina pentru generarea de numere in doua moduri:
MotoareUn motor e practic o sursa de numere uniform distribuite intre doua limite. Toate motoarele au urmatoarele functii:
Motoarele sunt de doua feluri: simple si compuse. Motoare simple:
Motoare compuse:
Pe langa acestea exista cateva typedef-uri dupa aceste motoare:
DistributiiIn TR1, o distributie este o clasa care transforma un flux de numere aleatoare uniform distribuite (obtinute de la un motor), intr-un flux de numere aleatoare, cu o distributie particulara. Cu alte cuvinte, numerele pseudo-aleatoare generate de un motor sunt intotdeauna uniform distribuite. Pentru a obtine o alta distributie pentru aceste numere ele trebuie trecute print-o distributie. Toate distributiile au urmatoarele metode:
In TR1 sunt definite urmatoarele clase de distributie:
Exemple de utillizareCea mai simpla forma de a genera numere aleatoare este de a folosi un generator. Exemplul de mai jos foloseste unul liniar congruent pentru a genera 10 numere aleatoare. Aceste numere sunt distribuite uniform in domeniul intreg.
// generator liniar congruent
std::tr1::minstd_rand gen;
// initializare generator
gen.seed((unsigned int)time(NULL));
// generare numere
for(int i = 0; i < 10; ++i)
{
std::cout << gen() << " ";
}
std::cout << std::endl;
In lipsa initializari, intotdeauna secventa va arata astfel: 48271 182605794 1291394886 1914720637 2078669041 407355683 1105902161 854716505 564586691 1596680831 Daca am vrea sa generam numere in intervalul [0, 9], atunci putem aplica un modulo 10 pe numerele generate.
for(int i = 0; i < 10; ++i)
{
std::cout << gen() % 10 << " ";
}
Acelasi efect, o secventa de 10 numere aleatoare in intervalul [0, 9], uniform distribuite poate fi obtinuta folosind generatorul combinat cu o distributie uniforma.
// generator liniar congruent
std::tr1::minstd_rand gen;
// distributie uniforma
std::tr1::uniform_int<int> dist(0, 9);
// initializare generator
gen.seed((unsigned int)time(NULL));
// generare numere
for(int i = 0; i < 10; ++i)
{
std::cout << dist(gen) << " ";
}
std::cout << std::endl;
O alta posibilitate este asocierea unui generator si a unei distributii prin clasa variate_generator.
// generator liniar congruent
std::tr1::minstd_rand gen;
// distributie uniforma
std::tr1::uniform_int<int> dist(0, 9);
// initializare generator
gen.seed((unsigned int)time(NULL));
// asociere generator-distributie
std::tr1::variate_generator<
std::tr1::minstd_rand,
std::tr1::uniform_int<int>> combgen(gen, dist);
// generare numere
for(int i = 0; i < 10; ++i)
{
std::cout << combgen() << " ";
}
std::cout << std::endl;
Daca initializarea generatorului s-ar fi facut dupa definirea lui combgen atunci secventa de numere ar fi fost intotdeauna aceiasi. // asociere generator-distributie std::tr1::variate_generator< std::tr1::minstd_rand, std::tr1::uniform_int<int>> combgen(gen, dist); // initializare generator gen.seed((unsigned int)time(NULL)); 0 6 8 9 1 5 3 2 7 0 Motivul este ca se face o copie a generatorului la instantierea lui combgen. Daca insa tipul generatorului ar fi unul referinta, atunci initializarea se poate face si dupa, intrucat se trimite o referinta. // asociere generator-distributie std::tr1::variate_generator< std::tr1::minstd_rand&, std::tr1::uniform_int<int>> combgen(gen, dist); // initializare generator gen.seed((unsigned int)time(NULL)); La fel ar sta lucrurile si in cazul unui tip pointer: // asociere generator-distributie std::tr1::variate_generator< std::tr1::minstd_rand*, std::tr1::uniform_int<int>> combgen(&gen, dist); // initializare generator gen.seed((unsigned int)time(NULL)); Daca nu se doreste ca numerele sa fie uniform distribuite, ci sa urmeze o alta distributie, de exemplu binomiala, nu trebuie decat folosit generatorul cu o instanta a acestei distributii:
// generator liniar congruent
std::tr1::minstd_rand gen;
// distributie binomiala
std::tr1::binomial_distribution<int, float> dist;
// initializare generator
gen.seed((unsigned int)time(NULL));
// generare numere
for(int i = 0; i < 10; ++i)
{
std::cout << dist(gen) << " ";
}
std::cout << std::endl;
Urmatorul exemplu arata cum se poate folosi un generator compus. Acesta este initializat nu folosind un numar, ci un numar aleator, returnat de alt generator.
// motoare
std::tr1::minstd_rand gen1;
std::tr1::mt19937 gen2;
std::tr1::linear_congruential<unsigned long, 33614, 0, 2147483647> seeder;
seeder.seed((unsigned int)time(NULL));
// motor combinat
std::tr1::xor_combine<
std::tr1::minstd_rand, // primul motor
7, // valoare de shiftare pentru primul motor
std::tr1::mt19937, // al doilea motor
13 // valoarea de shiftare pentru al doilea motor
> xorgen(gen1, gen2);
// distributie exponentiala
std::tr1::exponential_distribution<float> expdist(2);
// initializare generator
xorgen.seed(seeder);
// generare numere
for(int i = 0; i < 10; ++i)
{
std::cout << xorgen() << " ";
}
std::cout << std::endl;
ConcluziiClasele introduse in TR1 largesc mult posibilitatile de generare a numerelor aleatoare, cu o anumita distributie. Daca inainte erati nevoiti sa folositi o bibiloteca separata pentru a genera astfel de numere, acum aceste generatoare sunt disponibile in biblioteca standard. In plus, modalitatea de folosire a lor este destul de simpla si asemanatoare cu cea a lui rand(). |
|
Unelte:
|
