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?…

O profilowaniu, cyklach i kodzie z odzysku

Dla odmiany dzisiaj napisałem niewielką, ale bardzo wiele mówiącą o każdym kodzie rzecz – czyli profiler. Już wyjaśniam, że jest to moduł służący do kontrolowania wydajności: dzięki odpowiednio umieszczonym wywołaniom można przy jego pomocy określić, ile czasu zajmuje wykonywanie poszczególnych części programu.

Zasadniczą częścią jest tu oczywiście jakiś sposób pomiaru czasu. Dawniej, pisząc moduł profilujący, przygotowałem go tak, by oprócz czasu faktycznego w (mili/nano)sekundach podawał też ilość cykli procesora przypadających na daną operację. Na procesorach x86 można to zrobić przy pomocy rozkazu RDTSC. Obecnie porzuciłem tę koncepcję z kilku powodów, przy czym najbardziej prozaiczny jest ten, że… nigdy mi się taka funkcjonalność nie przydała :) Poza tym obecnie wartość zwracana przez wspomnianą instrukcję (a jest to liczba cykli procesora od momentu ‘resetu’) jest mało wiarygodna, jako że zdarzenia w rodzaju wstrzymywania czy hibernacji systemu bardzo lubią ją resetować. I wreszcie: ciężko jest przecież optymalizować kod pod kątem pojedynczych cykli procesora, jeśli pisze się głównie w języku wysokiego poziomu.
Wspomniałem, że to nie jest mój pierwszy profiler. W istocie, tak naprawdę dokonałem teraz zwyczajnego przepisania go (czy raczej drobnego przerobienia jego kodu) tak, by pasował do nowej wersji mojej biblioteki kodów wszelakich. (Bo cały czas bronię się, żeby nazywać ją silnikiem :)). W sumie więc nie jest to jakieś wielkie osiągnięcie, ale przynajmniej dowodzi tego, że kod napisany parę lat wcześniej nie musi od razu iść do kosza. Aczkolwiek jeśli chodzi o tę poprzednią wersję biblioteki, to raczej nic ciekawego już w niej nie znajdę :]

Wypadałoby teraz powiedzieć co nieco o tym, w jaki sposób tego starego-nowego profilera się używa. Otóż jest to całkiem proste. Bazując na jednym z rozdziałów pierwszego tomu Perełek programowania gier zorganizowałem pomiar czasu hierarchicznie. Można zatem korzystać z tego, że mniejsze operacje są częścią większych i tak je profilować – na przykład:

Dzięki temu można sprawdzać nie tylko maksymalny, minimalny i średni czas generowania całej ramki gry, ale też te same czasy osobno np. dla samego renderowania. Dalej można by jeszcze dodać statystyki dotyczącego tego, ile czasu (minimalnie, maksymalnie i średnio) zajmują procentowo czynności “mniejsze” względem “większych”.

Ale to już wymaga dopisania od podstaw, więc w przeciwieństwie do recyklingu starego kodu nie byłoby takie proste :)