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.

Reklamy

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

Agregaty kroczące

Rozważmy następującą sytuację: mamy w bazie danych rekordy zużycia jakiegoś zasobu oraz pulę do wykorzystania.

Na przykład rozliczamy jeden okres rozliczeniowy abonenta telefonu, ma on w ofercie jakąś ilość darmowych minut w każdym cyklu, więc gdzieś w bazie, w danych bilingowych w kolejnych rekordach ilości minut poszczególnych rozmów wchodzących w skład cyklu rozliczeniowego.

Interesująca nas część rekordu może się składać z dwóch kolumn: (id, minuty), gdzie większa wartość pola id oznacza późniejszy rekord. Chcemy napisać procedurę składowaną czy też funkcję, która w wyniku da nam zestawienie darmowych minut wykorzystanych w kolejnych rekordach, co z kolei w realnym systemie przełoży się na prawdziwy koszt kolejnych rozmów. Poniżej przykładowy wynik. Jego postać jest uzależniona od ilości minut w puli, tutaj pokazano ją  dla puli zawierającej 200 darmowych minut:

Id Minuty Darmowe Płatne
1 17 17 0
2 19 19 0
3 16 16 0
4 12 12 0
5 28 28 0
6 30 30 0
7 9 9 0
8 4 4 0
9 19 19 0
10 25 25 0
11 17 17 0
12 6 4 2
13 18 0 18
14 13 0 13
15 8 0 8
16 14 0 14
17 21 0 21
18 16 0 16
19 7 0 7
20 22 0 22
21 24 0 24
22 18 0 18
23 21 0 21
24 29 0 29

Zdefiniujmy w T-SQL prostą tabelę,  i wstawmy do niej dane tych przykładowych 24 rekordów:

CREATE TABLE Rozmowy
(
  Id int identity(1,1),
  Minuty int
 )

 INSERT INTO Rozmowy
 VALUES (17),(19),(16),(12),(28),(30),(9),(4),(19),(25),(17),(6),(18),(13),(8),(14),(21),(16),(7),(22),(24),(18),(21),(29)

Pierwsze podejście do problemu jest naturalne dla programisty języka wyższego poziomu. Załatwiamy sprawę w pętli – przy pomocy kursorów. W funkcji, której parametrem będzie pula minut, rekord po rekordzie generujemy wynikowy zbiór danych.

Czyli:

CREATE FUNCTION ZestawienieMinut
(@pula int)
RETURNS @tabela TABLE (Id int, Minuty int, Darmowe int, Płatne int)
AS
BEGIN
 DECLARE @id int
 DECLARE @minuty int
 DECLARE @suma int = 0  -- suma częściowa
 DECLARE @darmowe int = 0 -- wynikowa ilość darmowych minut

 -- Kursor przechodzący całą tabelę z rozmowami wg id
 DECLARE kursor CURSOR LOCAL FORWARD_ONLY FOR
	SELECT id, minuty FROM Rozmowy ORDER BY id

 OPEN kursor
 FETCH NEXT FROM kursor INTO @id, @minuty

 -- dopóki mamy co czytać
 WHILE @@FETCH_STATUS = 0
	 BEGIN

		IF @suma > @pula
			SET @darmowe = 0 -- już przekroczyliśmy pulę
		ELSE
			IF @minuty <= @pula - @suma  -- w bieżącym rekordzie jej nie przekraczamy
                SET @darmowe = @minuty
			ELSE						 -- bądź przekraczamy
				SET @darmowe = @pula - @suma

		-- tworzymy rekord wynikowy
		INSERT INTO @tabela values(@id, @minuty, @darmowe, @minuty - @darmowe)

		-- uaktualniamy sumę
		SET @suma = @suma + @minuty

		-- czytamy następny rekord
		FETCH NEXT FROM kursor INTO @id, @minuty
	END
  -- sprzątamy
  CLOSE kursor
  DEALLOCATE kursor
  RETURN
END

Działa? Działa. Ale mądry znajomy powiedział nam, że kursory to ZUO i że zawsze (no, może poza nielicznymi wyjątkowymi sytuacjami) da się zamiast kursora zastosować łączenie tabel i osiągnąć ten sam wynik na ogół z dużo większą wydajnością. Więc – jak tutaj sobie poradzić? Jeśli mamy charyzmę na takim poziomie, żeby przekonać wszystkich, że to na pewno jedna z tych wyjątkowych sytuacji, nie musimy robić nic. Jednak w przeciwnym wypadku, trzeba przedstawić inne rozwiązanie. Będą nim running totals, co podobno (tak mówi nasz lokalny firmowy ekspert baz danych) tłumaczy się na agregaty kroczące, moim zdaniem ładnie brzmi, nawet trochę mniej pośpiesznie niż oryginał (czyżby w Polsce stosowano zasadę A gentleman will walk, but never run?); jeśli chodzi o to, co mówią słowniki – moje poszukiwania zakończyły się znalezieniem banalnych sum częściowych.

Zatem, będziemy korzystać z agregatów, grupowania, sumowania. W rozwiązaniu z kursorami korzystaliśmy ze zmiennej @suma przechowującej sumę dotychczasowych przetworzonych wartości w rekordach i od niej uzależnialiśmy to, czy jeszcze darmowe minuty są, czy już minęły, czy może została ich tylko część ze wszystkich minut bieżącego rekordu. To właśnie ona będzie naszym agregatem kroczącym. Będziemy chcieli dla każdego rekordu zapytania w podzapytaniu taką sumę policzyć. Spróbujmy: dołączmy do naszej danej tabeli tę samą tabelę, tak żeby do każdego rekordu była dołączona suma wartości poprzednich rekordów oraz wartości z bieżącego rekordu. (Czemu dodajemy bieżący? Wolę dodać do sumy poprzednich wartość bieżącą niż się zastanawiać, co będzie, jeśli ja jestem pierwszym rekordem i w związku z tym moich suma poprzednich jest równa NULL). Czyli warunek łączenia będzie miał postać:

LEFT JOIN Rozmowy Rozmowy2 ON Rozmowy2.id<=Rozmowy.id

Grupować będziemy po całej wartości rekordu, do którego dołączamy, w końcu chcemy, żeby występował on raz. Czy oprócz sumy będziemy czegoś potrzebować? Tak. Jakiejś możliwości uzależnienia naszej wartości wynikowej od tej sumy i całkowitej puli minut. Dokładniej chodzi o zapisanie takiego warunku:

wynik = {jeśli suma poprzednich rekordów i mnie jest mniejsza od puli  ->    minuty;

jeśli suma poprzednich rekordów (beze mnie) jest większa lub równa puli -> 0;

a w przypadku pośrednim – pula – suma poprzednich rekordów (beze mnie)}

W podejściu iteracyjnym nie mieliśmy problemu, zmienne tymczasowe i jedna zagnieżdżona instrukcja if załatwiły sprawę. Tutaj kolejne instrukcje muszą być zastąpione wywołaniem jednej funkcji, jednak, jak się okazuje samej funkcji nie musimy pisać. T-SQL dysponuje konstrukcją case, która robi dokładnie to, o co nam chodzi – uzależnia wartość pola od wartości wyrażeń boolowskich.
W naszym przypadku dla pierwszego z wyliczanych pól konstrukcja będzie wyglądać tak:

CASE
	WHEN SUM(Rozmowy2.minuty) <= @pula
		THEN Rozmowy.minuty
	WHEN SUM(rozmowy2.minuty) - Rozmowy.Minuty >= @pula
		THEN 0
	ELSE
		@pula - (SUM(rozmowy2.Minuty) - Rozmowy.Minuty)
END as Darmowe

Drugie pole będzie wyglądało podobnie, jeśli chodzi o warunki, natomiast wartości mają dopełniać się z pierwszym polem do minut w rekordzie. Dzięki temu cała nasza funkcja będzie wyglądała następująco:

CREATE FUNCTION ZestawienieMinutBezKursorów
(
	@pula int
)
RETURNS TABLE
AS
RETURN
(
	SELECT Rozmowy.id, Rozmowy.minuty
	,CASE
		WHEN SUM(Rozmowy2.minuty) <= @pula
			THEN Rozmowy.minuty
		WHEN SUM(Rozmowy2.minuty) - Rozmowy.Minuty >= @pula
			THEN 0
		ELSE
			@pula - (SUM(Rozmowy2.Minuty) - Rozmowy.Minuty)
	 END AS Darmowe
	,CASE
		WHEN SUM(Rozmowy2.minuty) <= @pula
			THEN 0
		WHEN SUM(Rozmowy2.minuty) - Rozmowy.Minuty >= @pula
			THEN Rozmowy.Minuty
		ELSE
			 SUM(Rozmowy2.Minuty) - @pula
	END AS Płatne
	FROM Rozmowy
	 LEFT JOIN Rozmowy Rozmowy2
		ON Rozmowy2.id<=Rozmowy.id
	GROUP BY Rozmowy.id, Rozmowy.minuty
 )

Jej działanie możemy sprawdzić, pisząc:

SELECT Id, Minuty, Darmowe, Płatne FROM dbo.ZestawienieMinutBezKursorów(200) ORDER BY ID

(ORDER BY jest konieczne przy wywołaniu tego typu funkcji, ze względu na to, że serwer nie gwarantuje w żaden sposób kolejności rekordów zwracanych przez funkcję).

Jak widać, przy niewielkim wysiłku intelektualnym udało nam się zastąpić skomplikowaną i mało wydajną formułę iteracyjną na jedno zwięzłe zapytanie.

Przykład został zainspirowany walką z bardzo podobnym zapytaniem w Systemie Planowania Urlopów i Nieobecności (SPUiN).

10.03 '12 Posted by | Uncategorized | , | 1 komentarz

To ja, Czepialski

Czepialstwo jest tak mocno wpisane w moją naturę, że w jakiś sposób mnie definiuje.

Nie, nie czepiam się wszystkiego. Czepiam się głównie poprawności językowej na podstawowym poziomie. W informatyce niestety często.

Przykładowo – widzę niesamowite ilości zbędnych apostrofów. Po skrótach (np. *w WPF’ie zamiast w WPF-ie), po nazwiskach obcych w odmianie (np.  *Gates’a zamiast Gatesa), przed rokiem w formie 4-cyfrowej (*’2011).

Dalej – widzę dziwną wymowę. Informatycy wymawiają „delete” jak „dilejt” (zamiast „dylit„), często słyszy się „varchar” wymawiane jako „warczar” (ciekawe, że nikt nie wymawia „character” jako „czarakter”), no i nazwy interfejsów zakończone na -able wymawia się często z silnie akcentowanym „-ejbyl”.

No i w końcu widzę (i biadam nad tym), co się dzieje z językiem polskim: powstało dziwne słowo „wspierać”, które teraz już nie znaczy tyle, co wcześniej, czyli aktywnie pomagać komuś, czy podnosić kogoś na duchu. No bo jak to „wsparcie” ma się do tego, że program „wspiera” jakąś technologię?

Jeśli dodam, że uważam, że fraza „w czym mogę pomóc?” została wymyślona przez jakiegoś nieuka, który zapomniał, że istniał w polszczyźnie mocno zakorzeniony odpowiednik „czym mogę służyć?”, zostanę chyba uznany za człowieka nie z tej planety.

W podobnym miejscu sytuuje mnie moja skłonność do pisania kodu (nazw metod i zmiennych) po polsku. (W pracy piszę po angielsku, ale gdybym nie musiał, pisałbym po polsku).

Na koniec ciekawostka z wymowy angielskiej: „query does not rhyme with very„. Wiedzieliście? Ja nie wiedziałem, do czasu przeczytania wiersza „English Is Tough Stuff”, ale sprawdziłem w słowniku: rzeczywiście – query wymawia się mniej więcej jak kłiri.

Pozdrawiam i do roboty.

10.03 '12 Posted by | Uncategorized | Dodaj komentarz