Naprawdę duże liczby

Programując, rzadko mamy do czynienia z bardzo dużymi wartościami. Dowodem na to jest choćby fakt, że 32-bitowe systemy dopiero teraz zaczynają być w zauważalny sposób zastępowane 64-bitowymi. Jedynie w przypadku rozmiarów bardzo dużych plików operowanie zmiennymi mogącymi zmieścić wartości większe niż 4 miliardy jest konieczne.
Inne dziedziny życia i nauki przynoszą nam nieco większe wartości. Ekonomia czasami mówi o dziesiątkach bilionów (PKB dużych krajów), a fizyka często posługuje się wielkościami zapisywanymi przy pomocy notacji potęgowej – aż do ok. 10⁸⁰, czyli szacowanej liczby wszystkich atomów we Wszechświecie.

Wydawać by się mogło, że wielkość ta jest bliska górnej granicy wartości, jakich kiedykolwiek moglibyśmy używać w sensownych zastosowaniach. Okazuje się jednak, że tak nie jest; co więcej, jakakolwiek liczba zapisana za pomocą co najwyżej potęgowania jest tak naprawdę bardzo, bardzo mała.
Do zapisywania naprawdę dużych liczb potrzebne są bowiem inne notacje. Jednym z takich sposobów zapisu jest notacja strzałkowa Knutha, która jest “naturalnym” rozszerzeniem operacji algebraicznych. Tak jak dodawanie jest iterowaną inkrementacją, mnożenie jest iterowanym dodawaniem, a potęgowanie – iterowanym mnożeniem:

,

tak każdy następny operator strzałkowy jest iterowaną wersją poprzedniego. I tak pierwszy z nich, to zwykłe potęgowanie , ale już drugi:

jest odpowiednikiem wielokrotnego podnoszenia danej liczby do jej potęgi. W ogólności, skracając ciąg n strzałek do , otrzymujemy definicję:

Na pierwszy rzut oka może wydawać się to nieoczywiste, jednak już dla n = 3 i jednocyfrowych argumentów, wielkość liczb otrzymywanych przy użyciu notacji strzałkowej znacznie przekracza te, które można w wygodny sposób zapisać przy pomocy samego potęgowania. Chcąc je mimo wszystko przedstawić w tej postaci, trzeba się uciekać do sztuczek z klamerkami:

Oczywiście wraz ze wzrostem liczby strzałek nawet takie triki przestają wystarczać.

W tej chwili pewnie nasuwa się proste pytanie: czy z takiego systemu zapisu jest w ogóle jakiś pożytek, jeśli nikt nie posługuje się na poważnie tak wielkimi liczbami?… Odpowiedź jest jak najbardziej twierdząca, mimo że założenie w pytaniu jest nieprawdziwe. Otóż niektóre dziedziny matematyki używają nie tylko takich, ale i znacznie większych wartości – i nie chodzi tu nawet o teorię liczb, którą to jako pierwszą podejrzewalibyśmy o rzucanie liczbami “z kosmosu”.
Według Księgi Rekordów Guinnessa największą skończoną liczbą kiedykolwiek użytą w poważnym dowodzie matematycznym jest bowiem tzw. liczba Grahama, będącą górnym ograniczeniem pewnej wielkości występującej w problemie luźno związanym z grafami. Żeby ją zdefiniować, można użyć notacji strzałkowej – trzeba to jednak zrobić… iteracyjnie, wprowadzając pomocniczy ciąg g_n:

Już pierwszy jego wyraz nie daje się zapisać w postaci potęgowej, ale gwoździem programu jest zauważenie, że kolejne jego elementy posługują się poprzednimi w celu określenia liczby strzałek w operatorze . Innymi słowy, mamy tu wejście na kolejny poziom abstrakcji i stoimy już chyba tak wysoko, że aż strach spoglądać w dół ;)
Co jednak ze wspomnianą wcześniej liczbą Grahama? Teraz na szczęście jej określenie jest już bardzo proste. Jest ona równa ni mniej, ni więcej, jak tylko… g₆₄ :-)

Styl akcesorów

Ponieważ w C++ nie ma mechanizmu właściwości, do kontroli dostępu do pól w klasie wykorzystuje się metody dostępowe, czyli akcesory. Od kiedy zajmuję się programowaniem w tym języku, starałem się wynaleźć jakąś sensowną konwencję odnośnie tego, w jakiej postaci metody te zapisywać i jak je nazywać.
Niektórzy preferują na przykład utworzenie tylko jednej funkcji postaci:

która ustawia nową wartość pola i jednocześnie zwraca nam poprzednią. Takie rozwiązania realizuje chociażby funkcja set_new_handler, ustawiająca procedurę obsługi błędu braku pamięci dla operatora new. Nie akceptuję tego sposobu z jednego prostego powodu: bardzo częsta operacja pobrania wartości wymaga tutaj aż dwóch wywołań, które wyglądają co najmniej dziwnie.

Akcesory muszą więc być dwa (get/set). Pozostaje wtedy kwestia: jak je nazywać? Tutaj doszedłem do trzech możliwości:

1. Skorzystać z przeciążenia funkcji i obie metody nazwać tak samo, czyli po prostu X. Dla kompilatora będą one z łatwością odróżnialne, jako że getter jest bezparametrowy, a setter oczywiście nie.
2. Użyć nazw GetX i SetX.
3. Metodę zmieniającą nazwać SetX, ale getter po prostu X.

Chyba każdy z tych trzech sposobów widziałem w użyciu w jakiejś popularnej bibliotece, więc nie są to tylko teoretyczne propozycje. Sam zresztą wypróbowałem po kolei każdą z nich.

I tak rozwiązanie pierwsze jest na pewno najkrótsze, ale sprawia, że wywołania setterów wyglądają dziwnie. Widząc:

można zastanawiać się, co autor miał na myśli, a interpretacja “ustaw obiekt kamery dla sceny” nie musi być wcale tą, która nasuwa się jako pierwsza.
Z kolei drugi sposób (z Get/Set) jest całkowicie jednoznaczny, lecz w zamian potrafi wyprodukować łańcuszki w rodzaju poniższego:

Wszystkie te Gety trudno uznać za potrzebne do szczęścia, chociaż javowcy pewnie by się kłócili ;)

Dlatego też sposób trzeci polega na pozbyciu się ich (Getów, nie koderów Javy :>). Tę właśnie konwencję (SetX/X) wykorzystuję obecnie i jak dotąd stwierdzam, że sprawdza się dobrze. Dla ostatecznych wniosków byłby jednak potrzebny dłuższy okres, by przekonać się, czy po upływie pewnego czasu nadal mogę patrzeć na swój kod z zachowaniem równowagi psychicznej ;]

Piątek, trzynastego

W takim dniu jak dziś można zadać pytanie: czy programiści są przesądni? Wydaje się, że raczej nie – przynajmniej w porównaniu z niektórymi innymi zawodami (np. aktorzy teatralni mają tyle przesądów, że to cud, iż w ogóle wychodzą na scenę :]).

A jednak nie jest to wcale takie pewne. To przecież w informatyce ogóle, a w programowaniu w szczególności, wyeksponowaną pozycję zajmują wszelkiego rodzaju ‘zalecenia’, ‘dobre praktyki’ (best practices) i inne ‘rady’. Naturalnie, konsekwencje ich nieprzestrzegania nie są (zwykle) takie straszne – użycie dynamic_cast czy goto pewnie nie sprowadzi na nas siedmiu lat nieszczęść :) Mimo to da się odnaleźć sporo analogii.
Największą jest prawdopodobnie fakt, że w obu przypadkach nierzadko nie da się znaleźć sensownego, racjonalnego wytłumaczenia. Dotyczy to zwłaszcza tych zaleceń, w których sformułowaniu pojawiają się takie słowa-klucze jak ‘czytelność’, ‘przejrzystość’, ‘łatwość konserwacji’, a nawet ‘elegancja’. Żadnej z tych wartości nie da się obiektywnie zmierzyć i dla każdego mogą one mieć inne znaczenie. Pomimo tego faktu wiele osób skłonnych jest opierać o nie swoje kategoryczne twierdzenia o tym, jak programować należy lub nie należy. Jeśli dodatkowo osoby te cieszą się w środowisku autorytetem, to mają spore szanse na stworzenie ze swoich opinii pewnego rodzaju programistycznych przesądów, akceptowanych przez rzesze koderów bez większego zastanowienia.

Czy to jednak źle? Otóż wydaje mi się, że nie do końca. Tak jak każdy przesąd zawiera w sobie ziarnko prawdy (bo tłuczenie luster trudno uznać za bezpieczne zajęcie), tak owe dobre praktyki też mają na pewno wartość edukacyjną, zwłaszcza dla początkujących programistów. W najgorszym razie mogą nam służyć jako wskaźnik naszego poziomu umiejętności – odrzucenie naiwnej wiary, że od jednego goto cały kod zamieni się nam w spaghetti to dobry znak, że nabrało się już w kodowaniu pewnego doświadczenia :)

Bogata ikonografia

Zajmę się dzisiaj pewnym rodzajem aplikacji, którą przeciętny programista wykorzystuje rzadko, ale którą mimo tego powinien mieć. Mam tu na myśli program graficzny służący do edycji ikon, czyli tych małych (a od niedawna i większych) obrazków, które w Windows (i nie tylko) pojawiają się na każdym kroku – zwłaszcza na pulpicie czy w menu Start. Może nieczęsto zdarza się konieczność stworzenia ikonki dla własnej aplikacji, lecz kiedy już trzeba to zrobić, warto posłużyć się w tym celu odpowiednim narzędziem (a nie Paintem na przykład :]).
Znalezienie dobrej i darmowej aplikacji do edycji ikon nie jest jednak takie łatwe, jako że najlepsze i najpopularniejsze z nich są licencjonowane jako shareware. Istnieje jednak przynajmniej jeden darmowy i wart polecenia program tego typu; sam dowiedziałem się o nim od Rega.

Nazywa się on IcoFX i ze względu na swą niepozorną wielkość (1.5 MB) ma chyba jedną z lepszych proporcji użyteczności do rozmiaru. Zawiera on bowiem zdecydowaną większość funkcji (jeśli nie wszystkie), jakie można wymagać od tego rodzaju aplikacji.
Program ten obsługuje oczywiście wszystkie używane obecnie rozmiary (od 16×16 do 256×256), głębie kolorów (od 1 do 32 bitów z kanałem alfa) i formaty ikon (łącznie z PNG wykorzystywanym od Visty wzwyż). Oprócz całego wachlarza typowych narzędzi graficznych oferuje też wiele predefiniowanych filtrów (rozmycie, detekcja krawędzi itp.) wraz z możliwością definiowania własnych. Generalnie część “graficzna” programu jest bez zarzutu. Jedynym mankamentem, na jaki się zdołałem dotąd natknąć, jest brak możliwości określania tolerancji kolorów dla wypełniania typu flood fill.

Część “narzędziowa” też prezentuje się dobrze. Przy pomocy programu możemy nie tylko ekstrahować ikony z plików .exe i .dll (w razie potrzeby masowo przy pomocy batch processing), ale także edytować takie pliki (w zakresie ikon, rzecz jasna). Taka edycja mogłaby być wprawdzie nieco lepiej pomyślana (dodanie nowej ikony do pliku .exe/.dll jest możliwe tylko poprzez import z .ico), ale w sumie da się z nią wytrzymać.

Tak więc na te niezbyt częste okazje, gdy musimy/chcemy pobawić z ikonami, IcoFX wydaje się ogólnie całkiem dobrym rozwiązaniem. Zwłaszcza ze tę cenę :)

Wartość pomysłów

Podobno w informatyce najcenniejszym zasobem są pomysły. Bo o ile zrealizowanie gotowej idei to praca czysto rzemieślnicza i – przynajmniej teoretycznie – możliwa zawsze do wykonania przy odpowiednim czasie i przy właściwej liczbie osób, to z kolei “wzięcie skądś” pomysłu nie jest taką prostą sprawą. W końcu, jak to ktoś powiedział, pomysły nie rosną przecież na drzewach :)

Tak to zwykle wygląda z rynkowego punktu widzenia. Dlatego bardzo ciekawy jest fakt, że np. na Warsztacie wygląda to – jak się wydaje – zupełnie odwrotnie. Objawem tego jest choćby fakt, że działy z pomysłami i projektami na forum są jednymi z większych i bardziej aktywnych. Jak to możliwe?
Wydaje mi się, że przyczyny są co najmniej dwie. Po pierwsze, na Warsztat trafiają osoby zainteresowane programowaniem gier i przynajmniej część z tych (a w rzeczywistości pewnie całkiem spora część) chcę zająć się tym tematem między innymi dlatego, że mają w głowie pomysł na jakąś grę. Albo na kilka od razu. A że na początkowym etapie nauki nijak nie da się tego zrealizować, owe genialne idee lądują we wspomnianym dziale forum.
Poza tym, nie ma co ukrywać: większość z nich jest w istocie marnej jakości – nawet jeśli litościwie odsiejemy projekty kolejnych MMORPG-ów, jakie dość często się pojawiają :) Oczywiście dla swoich autorów są one zawsze niezwykle innowacyjne i warte zrealizowania, ale nie łudźmy się: tak naprawdę podobne epitety można przypisać tylko ich małemu ułamkowi.

Innymi słowy, jest duża różnica pomiędzy pomysłem a dobrym pomysłem. Tych pierwszych każdy z nas ma pewnie dziesiątki tygodniowo. Nieuchronnie trzeba więc wybierać z nich tylko te najbardziej wartościowe. Do pozostałych najlepiej jest zaaplikować garbage collector :)

Nowoczesne wyliczanie

W chyba każdy języku posiadającym pojemniki (jak wektory czy listy) istnieje koncepcja iteratorów: obiektów, które pozwalają na przeglądanie kolekcji i są uogólnieniem wskaźników. W najprostszym pozwalają one tylko na pobranie aktualnego elementu i przejście do następnego, ale jest to zupełnie wystarczające do celów wyliczania.
Z wierzchu więc wyglądają one całkiem prosto i przejrzyście – zwłaszcza, jeśli język udostępnia pętlę typu foreach, która ładnie i przezroczyście je opakowuje. Dlatego może wydawać się dziwne, czemu zazwyczaj mechanizm ten jest używany właściwie tylko dla pojemników; w teorii bowiem za pomocą iteratorów (zwanych gdzieniegdzie enumeratorami) można by było przeglądać dosłownie wszystko.
Weźmy chociażby wyszukiwanie plików na dysku – sporo programów w jakimś momencie swojego działania musi znaleźć pliki np. o danej nazwie w określonym katalogu. Wtedy zwykle zakasujemy rękawy i piszemy odpowiednią procedurę rekurencyjną lub bawimy się ze stosem czy kolejką. A czy nie fajniej byłoby, gdyby dało się to zrobić po prostu tak:

oczywiście przeszukując w ten sposób również podkatalogi bez jawnego “wchodzenia” do nich?… Według mnie to by było bardzo fajne :)

Od razu zaznaczę więc, że wbrew pozorom taki iterator jest jak najbardziej możliwy do napisania. Problemem jest jednak to, jak należy przechowywać jego stan. Kiedy wyszukiwanie czy przeglądanie zaimplementowane jest bezpośrednio jako jedna funkcja, robi się to w zasadzie samo: w postaci zmiennych lokalnych (stos/kolejka) albo parametrów (rekurencja). Nikt specjalnie nie zwraca na ten fakt uwagi. Jednak w momencie próby “wyciągnięcia” z algorytmu operacji Next (w celu stworzenia iteratora) okazuje się nagle, że wymaga to jawnego pamiętania tych wszystkich danych, które pozwalają obliczyć następny element. Przy przeszukiwania katalogów trzeba by na przykład pamiętać jakiś systemowy uchwyt wyszukiwania dla aktualnego katalogu, poziom zagnieżdżenia oraz analogiczne uchwyty… dla każdego takiego poziomu!
Zawracanie głowy, prawda? :) Nic dziwnego, że traktowanie wyszukiwania “per iterator” nie jest popularną praktyką. Z punktu widzenia piszącego algorytm wyliczania nieporównywalnie łatwiej jest po prostu wymusić jakiś callback i wywołać go dla każdego elementu; niech się programista-klient martwi o to, jak ten callback wpasować w swój kod. A że ten byłby o wiele czytelniejszy, gdyby w grę wchodziły iteratory? No cóż, iteratorów tak łatwo pisać się nie da…

…chyba że programujemy w Pythonie. Tam bowiem “iteratory” (zwane generatorami) piszemy w zupełnie unikalny, łatwy sposób. Weźmy dla przykładu taką oto klasę drzewa binarnego (BST – Binary Search Tree):

I już – to wystarczy, by poniższa pętla:

rzeczywiście “chodziła” po krawędziach drzewa “w czasie rzeczywistym” – bez żadnego buforowania elementów na liście.

Tajemnica tkwi tutaj w instrukcji yield – działa ona jak “tymczasowe zwrócenie” elementu, który jest przetwarzany przez ciało pętli for. Gdy konieczny jest następny element, funkcja inorder podejmuje po prostu działanie począwszy od kolejnej instrukcji – i tak do następnego yielda, kolejnego cyklu pętli i dalszej pracy funkcji. yield działa więc jak callback, tyle że w obie strony. Całkiem zmyślne, czyż nie?
Aż chciałoby się zapytać, czy w innych językach – zwłaszcza kompilowanych – nie dałoby się zrobić czegoś podobnego. Teoretycznie odpowiedź jest pozytywna: przy pomocy zmyślnych sztuczek na stosie wywołań funkcji (technika zwana ‘nawijaniem stosu’ – stack winding) można uzyskać efekt “zawieszenia funkcji” po zwróceniu wyniku i mieć możliwość powrotu do niej począwszy od następnej instrukcji. Nie jestem jednak przekonany, jak taki feature mógłby współpracować z innymi elementami współczesnych języków programowania, jak choćby wyjątkami. Trudno powiedzieć, czy jest to w ogóle możliwe.

Ale skoro w Pythonie się da, to może już C++2x będzie to miał? ;-)

Triki z PowerShellem #11 – Ćwierkamy

W ramach wyposażania nowozainstalowanego systemu w niezbędne programy, przypomniałem sobie o istnieniu PowerShella. Kiedy jednak chciałem go ściągnąć, spotkała mnie przyjemna niespodzianka: PSh w Windows 7 jest już od razu zainstalowany, więc można go od razu zacząć go używać. Jak sądzę, przyczyni do zwiększenia jego popularności, co jest z pewnością dobrą rzeczą.

Fakt sprawił rzecz jasna, że zaraz zachciało mi się wypróbować go w jakimś nowym zastosowaniu. Padło na wysyłanie update‘ów do Twittera, w którym to zresztą niedawno się zarejestrowałem (i wciąż nie wiem, dlaczego ;)). Sprawa na oko nie jest trudna, bo sprowadza się do wykonania jednego żądania HTTP POST. Ale jak wiadomo, diabeł zwykle tkwi w szczegółach. Oto skrypt:

Jednym z owych detali było kodowanie statusu algorytmem dla URL-i (zamieniającym spacje na %20 itd.), wykonywane poprzez System.Web.HttpUtility.UrlEncode – stąd konieczność importowania assembly System.Web. Ale to jest w sumie pikuś.
Znacznie większym “trikiem” jest linijka oznaczona gwiazdką (*). Powoduje ona obejście domyślnego zachowania .NET, który do każdego żądania HTTP typu POST dodaje nagłówek:

Powoduje on wysłanie tak naprawdę dwóch requestów: w pierwszym serwer ma tylko sprawdzić poprawność nagłówków (logowania, na przykład) i zwrócić status 100 (Continue). Dopiero w drugim klient wysyła właściwe dane. Mechanizm ten jest w .NET opakowany przezroczyście i ma zapobiegać niepotrzebnemu przesyłaniu dużych ilości danych w żądaniu, które i tak byłoby odrzucone.
API Twittera jednak tego nie obsługuje i jest to właściwe. Trudno przecież nazwać status, mający maks. 160 znaków, “dużą ilością danych”. Lepiej więc przesyłać go od razu, a domyślne zachowanie .NET-a obejść. To właśnie robi zaznaczony wiersz.

Przypomnę jeszcze tylko – gdy ktoś zechciał powyższego skryptu używać do przesyłania tweetów – że uruchomienie skryptu PSh z poziomu zwykłej linii poleceń wymaga parametru -Command i kropki:

Do takiej komendy można np. utworzyć skrót i przypisać mu kombinację klawiszy w celu szybkiego uruchamiania.