Czepialski programista

refleksje przy programowaniu w .net i t-sql

O liczbach losowych

Napiszmy prosty program, który rzuca 10 razy kostką.

    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 0; i < 10; i++)
                Console.WriteLine(new Random().Next(6) + 1);
        }
    }

Aplikacja konsolowa, wpisujemy, uruchamiamy. Wynik jednak nie jest specjalnie zadowalający. W moim przypadku kostka była monotonna. Zazwyczaj wypadło 10 razy to samo; raz na kilka uruchomień się zdarzało, że cykl się zmieniał – np. po dwójkach zaczęły wypadać czwórki, ale też nic więcej.

O co chodzi? Przecież za każdym razem mamy nowy (new) generator liczb losowych, a jak nowy, to chyba nie powinien pamiętać o starych liczbach.

Zanim napiszę, dlaczego to nie działa – prosta zmiana, która pomoże na szybko przerobić program, żeby dawał rozsądne wyniki.

    class Program
    {
        static void Main(string[] args)
        {
            var gen = new Random();
            for (int i = 0; i < 10; i++)
                Console.WriteLine(gen.Next(6) + 1);
        }
    }

Teraz program już działa zgodnie z oczekiwaniami.

Widzimy, że zmiana polegała na tym, że teraz mamy jeden generator, generujący kolejne liczby. W czym kilka generatorów jest gorszych od jednego? Nie byłyby wcale gorsze, ale tak naprawdę to nie jest kilka generatorów, a góra jeden, dwa. Sekret tkwi w konstruktorze obiektu klasy Random. Standardowy generator, jaki nam udostępnia przestrzeń nazw System to generator z jednym parametrem. Parametr ten określa się słowem seed, co tłumaczy się czasem jako zarodek, a czasem w ogóle się nie tłumaczy. Zasada jest taka: tworzymy generator z określonym zarodkiem – daje on te same wyniki (ten sam cykl kolejnych wygenerowanych liczb), jak drugi generator z tym samym zarodkiem. Możemy sobie w ten sposób zapewnić powtarzalność.

Na przykład, jeżeli w naszym programie w linii 5. napisalibyśmy:

            var gen = new Random(17);

Otrzymalibyśmy w każdym wywołaniu programu następującą sekwencję liczb:

4, 5, 4, 2, 6, 3, 4, 6, 1, 4

No dobrze, więc co z tym konstruktorem bezparametrowym? Tutaj jakby nie ma tego seeda czy jak mu tam.

Seed zawsze jest, bo musi być. I w przypadku konstruktora bezparametrowego jest ustawiany wg tzw. czasu systemowego. Dokumentacja msdn nie mówi zbyt dużo o nim: „The default seed value is derived from the system clock and has finite resolution„. Ale to wystarczy: ta skończona dokładność, czyli długość kwantu czasu tego zegara systemowego wynosi ok. 10 ms. Co się przekłada na to, że jeśli w ciągu tego 10-milisekundowego kwantu skonstruujemy więcej obiektów klasy Random, będą one miały ten sam zarodek. Kolejne instrukcje w programie przetwarzane są w czasie rzędu już nie milisekund, a raczej nanosekund. (Kto chce, niech sprawdzi, w jakim czasie wykona się milion razy pętla, w której w środku jest jedna instrukcja). Więc – nic dziwnego, że nasza kostka oszukiwała. Rzucaliśmy nią tak naprawdę tylko raz, a potem przypominaliśmy sobie kolejnych 9 razy, ile wypadło za pierwszym razem.

Jako dobrą praktykę programistyczną podaje się tworzenie w takich sytuacjach jednego generatora liczb na całą klasę, a nawet na całą aplikację, i brania z niego za pomocą metod typu Next kolejnych liczb. Taki generator mógłby być przechowywany w publicznej właściwości statycznej, w jakiejś klasie pomocniczej, dzięki czemu dostęp do niego w aplikacji nie byłby ograniczony.

Problemem jest jednak użycie takiej właściwości w aplikacjach wielowątkowych – klasa Random nie jest thread-safe, czyli mogą pojawić się problemy synchronizacji w wątkach, np. wielokrotne wykorzystanie w kolejnych wywołaniach tej samej liczby z sekwencji. Zapobiec można temu dzięki konstrukcji typu thread-local storage, czyli tworzenia pól, które są widziane w obrębie swojego wątku (co znaczy, że każdy wątek ma swoją instancję). W C# tworzy się je za pomocą generycznej klasy System.Threading.ThreadLocal:

        static ThreadLocal<Random> r;

Jeśli chcemy użyć inicjalizatora pola, możemy – przy użyciu wyrażeń lambda:

        static ThreadLocal<Random> r = new ThreadLocal<Random>(() => new Random());

Klasa ThreadLocal jest dostępna w .Net Framework od wersji 4.0. We wcześniejszych wersjach bibliotek można było statyczne pola, które miały być lokalne dla wątku, oznaczać atrybutem [ThreadStatic], ale niestety nie dało się ich inicjalizować (inicjalizowane były raz, a nie w każdym wątku osobno).

Na koniec uwaga dla ludzi, którzy chcieliby wykorzystywać klasę Random do celów kryptograficznych. Nie róbcie tego, ta klasa jest łatwa do rozszyfrowania. Do tych celów została zaprojektowana klasa RandomNumberGenerator w przestrzeni nazw System.Security.Cryptography. Jej interfejs jest dużo uboższy niż standardowego Random, ale można jej ze spokojem używać do celów bezpieczeństwa.

Dziękuję za inspirację Markowi Ozaistowi.

W zakończeniu artykułu wykorzystałem informacje z książki „C# 4.0 in a Nutshell” autorstwa Josepha i Bena Albaharich.

20.03 '12 Posted by | Uncategorized | , , | 5 Komentarzy