Ujemna wartość bezwzględna?…

Każdemu absolwentowi szkoły podstawowej (mam nadzieję, że wciąż podstawowej…) powinna być znana poniższa funkcja:

Tak, jest to zwyczajna wartość bezwzględna, znana również jako moduł liczby. Jej formalna definicja gwarantuje, że dla każdego . Innymi słowy, wartość bezwzględna nigdy nie może być ujemna. Nic więc dziwnego, że używamy jej chętnie w tych właśnie sytuacjach, gdy interesuje nas tylko dodatnia połowa osi liczb. Oto bardzo prosty przykład:

Mamy tu elementarną sztuczkę, polegającą na początkowym przypisaniu polu identifier wartości spoza zwykłej dziedziny (-1), co oznaczać ma brak identyfikatora. Możemy tak zrobić, bo dzięki wartości bezwzględnej (funkcji Math.abs) generowane losowe identyfikatory będą zawsze dodatnie.

Albo raczej prawie zawsze…

Eksperyment z losowymi ciągami

Zdarzyło się dzisiaj, że musiałem zaimplementować rozwiązanie wyjątkowo klasycznego problemu. Siląc się matematyczny formalizm, mógłbym go zdefiniować następująco:

• Mamy dany zbiór dowolnych elementów oraz liczbę naturalną .
• Szukamy ciągu k elementów .

Krótko mówiąc, chodzi o trywialną wariację z powtórzeniami. Ambitne to zadanie jest w sumie nawet mniej skomplikowane niż częste ćwiczenie dla początkujących pt. losowanie Lotto, więc po chwili wyprodukowałem coś podobnego do kodu poniżej:

I na tym pewnie historia by się zakończyła, gdybym nie przypomniał sobie, że Python domyślnie potrafi obsługiwać naprawdę duże liczby. (Może nie aż tak duże jak te tutaj, ale jednak dość spore ;]). Obserwacja ta daje się bowiem połączyć z inną: taką, iż ciąg elementów z pewnego zbioru jest równoważny liczbie w systemie o podstawie równej mocy tego zbioru. Taka liczba jest oczywiście bardzo duża w prawie każdym praktycznym przypadku, lecz to nie umniejsza w niczym prawdziwości stwierdzenia. Jest ono zresztą z powodzeniem wykorzystywane w systemach kryptograficznych w rodzaju RSA.

Postanowiłem więc i ja z niego skorzystać. Przynajmniej teoretycznie fakt ten powinien dawać lepsze rezultaty, zamieniając k losowań na tylko jedno – tak jak poniżej:

Doświadczenie z kolei uczyłoby, że bezpośrednie aplikowanie dziwnych matematycznych koncepcji do programowania rzadko miewa dobre skutki ;) Jak więc jest w tym przypadku?…

Unikalne łańcuchy znaków

Okazjonalnie zachodzi potrzeba, aby do jakiegoś celu wygenerować niepowtarzalny ciąg znaków. Jednym z zastosowań może być tutaj nadanie plikowi nazwy gwarantującej brak kolizji z jakąkolwiek inną nazwą pliku w systemie albo chociaż w aktualnym katalogu. W przypadku gdy ów plik ma istnieć tylko przez chwilę – a więc być plikiem tymczasowym (tempfile), sprawa jest prosta i sprowadza się do wywołania GetTempFileName jako funkcji WinAPI lub metody klasy System.IO.Path z .NET.

Stworzona w ten sposób nazwa jest z definicji “krótko żyjąca”. Na drugim biegunie w zakresie unikalności znajdują się tzw. UUID-y, czyli specjalnie ustandaryzowane 128-bitowe identyfikatory konstruowane tak, by zapewnić, że prawdopodobieństwo wygenerowania duplikatów jest mikroskopijnie małe. Każdy, kto grzebał trochę w Rejestrze Windows lub miał do czynienia z technologią COM, zna na pewno ich kuzynów, czyli GUID-y, opartych w gruncie rzeczy na podobnych zasadach.
Ponieważ tworzenie nowych GUID-ów/UUID-ów jest proste, można je wykorzystać w celu uzyskania niepowtarzalnych ciągów znaków. W czystym Windows API unikalny string oparty na UUID-zie można otrzymać np. tak:

Z kolei w .NET istnieje wyspecjalizowana klasa System.Guid, którą można wykorzystać w podobnym celu. W wyniku otrzymamy oczywiście teksty w stylu:

0DF44EAA-FF21-4412-828E-260A8728E7F1

co w wielu zastosowaniach może być strzelaniem z armaty do komara. Nie zawsze potrzebujemy przecież aż tak wielkiej unikalności, a UUID-y w formie tekstowej są długie i nieporęczne.

Są więc i inne rozwiązania, stosowalne jeśli nasz losowy ciąg musi być unikalny tylko przez stosunkowo niedługi czas, np. podczas jednego uruchomienia programu. W takim wypadku możemy użyć chociażby:

• wartości zwracanych przez GetTickCount/QueryPerformanceCounter lub asemblerową instrukcję rdtsc. Jest to czas (lub liczba cykli procesora) od momentu rozruchu systemu, więc z definicji wartość taka nie powtórzy się w trakcie działania aplikacji. Warto wiedzieć aczkolwiek, że używanie rdtsc jest generalnie niezalecane.
• aktualnego systemowego czasu – pobranego przez GetSystemTime z Windows API czy System.DateTime.Now z .NET – przekonwertowanego na string. Wadą jest tutaj wynikowa długość łańcucha i zbyt oczywisty format; prawdopodobnie więc należałoby jeszcze poddać go jakiemuś post-processingowi.
• zwykłego ciągu losowych znaków. W zależności od jakości generatora liczb losowych oraz losowości początkowego ziarna seed, możemy otrzymać nawet całkiem dobre wyniki. Metoda jest dobra zwłaszcza wtedy, gdy generowanych identyfikatorów jest na tyle mało, że możemy je efektywnie przechowywać i po prostu sprawdzać, czy nowy string jeszcze nie wystąpił (przykładem mogą być uchwyty w menedżerze zasobów w silniku gry).

Najważniejsze jest to, aby właściwie dobrać metodę do sytuacji, w której potrzebujemy unikalnego łańcucha znaków. Często wystarczy coś w stylu:

Nie myślmy nawet jednak, żeby tak stworzonego stringa używać do jakiejkolwiek formy komunikacji przez sieć. W takich przypadkach trzeba w zasadzie użyć UUID-ów.

Boost i liczby losowe

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ą :)

Losowanie tabelkowe

W niemal każdym programie chociaż raz zdarza się potrzeba, by “rzucić kośćmi” i pozwolić, by wydarzyło się coś losowego. Oznacza to skorzystanie z generatora liczb pseudolosowych, aby uzyskać ‘przypadkową’ wartość. Nie będzie ona faktycznie losowa, lecz dzięki zastosowaniu matematycznych formuł o dużej nieregularności rezultat może być bardzo zbliżony do ideału. Istnieje oczywiście wiele algorytmów wyznaczania liczb pseudolosowych, różniących się faktyczną przypadkowością uzyskiwanego wyniku.
W różnych językach programowania mamy natomiast odmienne sposoby na uzyskanie liczby ‘losowej’. Zwykle najwygodniejszym jest wartość z zakresu [0..1], bo odpowiada to matematycznemu pojęciu prawdopodobieństwa. Aby w C++ uzyskać taki rezultat, wystarczy napisać proste opakowanie na biblioteczną funkcję rand:

Mając taki generator, możemy już łatwo sprawdzić, czy “zdarzyło się” coś, czego prawdopodobieństwo znamy:
// doświadczenie losowe z określonym prawdopodobieństwem
bool RandomOccured(float fProbability) { return Random() <= fProbability; }[/cpp] W ten sposób możemy na przykład rzucać wirtualną monetą. Sprawa się jednak komplikuje, jeżeli możliwych wyników doświadczenia jest więcej, a przy okazji mają one różne prawdopodobieństwa zajścia. Tak się dzieje na przykład w grach RPG, w których konieczne jest obliczanie rezultatów zadanych ciosów (trafienie, pudło, unik, blok, itp.). Skuteczność postaci w walce zależy zwykle od jej statystyk, więc szanse poszczególnych wyników nie są stałe i zmieniają się w trakcie gry.
Dobre generatory liczb pseudolosowych są zaś nierzadko względnie kosztowne obliczeniowo. Dlatego zamiast wykonywać po jednym losowaniu dla każdego możliwego rezultatu (zaszedł – nie zaszedł), znacznie lepiej jest załatwić wszystko jednym losowaniem. Nie jest to trudne:
// doświadczenie losowe z prawdopodobieństwem określonym tabelką
int RandomResult(const float* aProbs, int n)
{
float fRand = Random();

float fAccum = 0.0f;
for (int = 0; i < n; ++i) { // sprawdzamy, czy wylosowana liczba mieści się w zakresie p-stwa if (fAccum <= fRand && fRand < fAccum + aProbs[i]) return i; fAccum += aProbs[i]; } // błąd return -1; }[/cpp] Tak naprawdę liczymy tutaj dla każdego możliwego rezultatu wartość tzw. dystrybuanty. Ale chyba nie warto wnikać w takie teoretyczne szczegóły – grunt, że powyższa metoda działa w praktyce :) Trzeba tutaj jednak pamiętać, aby prawdopodobieństwa sumowały się do 1. Jeśli tak nie jest, można przeskalować wylosowaną liczbę.