xion.log » Boost i liczby losowe

Boost i liczby losowe

2009-06-09 17:31

Narzekanie na jakość generatorów liczb (pseudo)losowych wbudowanych w języki programowania (takich jak rand() w C/C++) to dość popularne zajęcie wśród programistów gier. Chociaż nierzadko jest ono raczej bezpodstawne (albo ma charakter martwienia się na zapas), to niekiedy faktycznie losowość (czy raczej: nieregularność) uzyskiwanych wyników pozostawia wiele do życzenia.
Oczywiście zagadnienie generowania liczb “losowych” doczekało się mnóstwa opracowań jeszcze na długo przed tym, zanim stały się one potrzebne do wyliczania ruchu piłeczki odbitej od paletki w Pongu :) W praktyce możemy więc znaleźć mnóstwo dobrze działających implementacji różnego rodzaju generatorów liczb pseudolosowych dla większości znanych we Wszechświecie języków programowania.

Wspominam o tym, bo ostatnio sam potrzebowałem czegoś podobnego w C++. A gdzie zagląda każdy programista tego języka, gdy czegoś mu brakuje?… Do Boosta naturalnie :) Jako że jest tam (prawie) wszystko, niespecjalnie zdziwiło mnie, że istnieje cała biblioteka od szeroko pojętej losowości – Boost.Random. Zawiera ona rzecz jasna implementacje kilku różnych generatorów liczb pseudolosowych, różniących się nieregularnością wyników, szybkością, wymaganiami pamięciowymi, itd.
Tak naprawdę jednak tym, co czyni tę bibliotekę interesującą, jest sposób łączenia tych generatorów z wieloma dostępnymi tam rozkładami liczb losowych. Jeśli ktoś przysypiał na lekcjach matematyki lub wykładach z rachunku prawdopodobieństwa, to przypomnę, że – najprościej mówiąc – rozkład określa nam, jakie wartości mogą być wylosowane i jakie jest prawdopodobieństwo uzyskania każdej z nich. Przykładowo, standardowy rand teoretycznie oferuje nam liczby losowe o rozkładzie jednorodnym na zbiorze { 0, 1, …, RAND_MAX-1 }. Oznacza to, że – gdyby losowość była tu rzeczywista, a nie udawana – każda z tych wartości ma taką samą szansę na bycie wylosowaną. W przypadków innych rodzajów rozkładów nie musi tak być i niektóre wyniki mogą być bardziej preferowane niż inne (niezależnie od jakości generatora).

Jak więc wygląda to w Boost.Random? Ano całkiem zgrabnie. Najpierw bowiem wybieramy używany generator liczb, a potem pożądany rozkład, i obie te rzeczy możemy połączyć w jeden poręczny obiekt. Oto przykład:
#include

// generator liczb losowych
// (jest to pewna wersja znanego algorytmu Mersenne Twister)
boost::mt19937 rng;

// docelowy rozkład otrzymywanych liczb
// (jednorodny rzeczywisty na przedziale -1…1)
boost::uniform_real dist(-1, 1);

// wynikowy obiekt
boost::variate_generator >
random(rng, dist);

// kilka losowań
for (int i = 0; i < 10; ++i) std::cout << random() << std::endl;[/cpp] Jak nietrudno zauważyć, ten przykład pokazuje, jak bardzo C++ potrzebuje obecnego w C# od wersji 3.0 słowa kluczowego var ;-) Poza tym jednak widzimy, że otrzymany obiekt jest w użyciu bardzo prosty: aby dostać następną losową liczbę, wystarczy po prostu użyć na nim operatora (). Rezultat będzie od razu z właściwego przedziału (nie trzeba żadnych mnożeń czy dzieleń modulo), który określamy, definiując rozkład. Tutaj jest on jednorodny, ale oczywiście w Boost.Random mamy też mnóstwo innych, jak choćby geometryczny, wykładniczy, Gaussa (normalny), Bernoulliego, itp.
Nie to żeby były one jakoś często potrzebne, ale kiedy trafi się – tak jak mi – konieczność użycia któregoś z nich, to dobrze jest mieć tę bibliotekę pod ręką :)

Tags: ,
Author: Xion, posted under Programming »


10 comments for post “Boost i liczby losowe”.
  1. 3val:
    June 10th, 2009 o 8:08

    Co do słówka var, to w booście jest BOOST_AUTO ;)

  2. zwierzak:
    June 10th, 2009 o 9:23

    W C++0x (pewnie będzie c++10, ze względu, że ma wyjść najwcześniej w przyszłym roku) będzie słówko auto, we wczesnych buildach gcc i vc++ już jest dostępne.

  3. Dabroz:
    June 10th, 2009 o 15:20

    A jak z wydajnością tego boostowego rand?

  4. vashpan:
    June 10th, 2009 o 17:57

    “auto” za to juz jest w D, jak zapewne wiekszosc tego co programista C++ chcialby miec w swoim wymarzonym jezyku ;)

  5. Aithne:
    June 10th, 2009 o 20:10

    Powiedz, jak ten kod skończy się kompilować ;).

  6. Xion:
    June 11th, 2009 o 14:01

    Jeśli chodzi o wydajność generatorów, to zgodnie z tabelką w dokumentacji boosta jest całkiem dobrze. mt19937 jest podobno 5 razy szybszy od generatora z C, a w przypadku innych różnica jest nawet większa. Ceną za to jest oczywiście większa zajętość pamięci przeznaczonej na stan generatora.

  7. Aithne:
    June 12th, 2009 o 17:58

    Jeszcze się kompiluje…?

  8. Jarosz:
    June 17th, 2009 o 10:50

    http://gamesbyemail.com/News/DiceOMatic

  9. RRRRRRRR:
    June 17th, 2009 o 12:14

    Chłopie! Lepiej usuń ten stek bredni o C++,
    jakim jest Twój “megatutorial”.
    Za jego pomocą tylko ogłupiasz młodzież.
    A może to jest właśnie Twoim celem, co?

  10. Maxi:
    June 17th, 2009 o 14:05

    Ja tam się cieszę, że są tu tematy takie jak ten. Osobiście ucieszył bym się jeszcze bardziej jakbyś napisał coś o sposobie w jaki działają obiekty funkcyjne i adaptery z STLa oraz jak i kiedy pisać własne.

Comments are disabled.
 


© 2018 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.