Maksimum, minimum

Programiści grafiki czasu rzeczywistego wiedzą, że gdy w obliczeniach potrzebne są wartości sinusa i cosinusa dla tego samego kąta, należy obliczać je razem. (O ile oczywiście ich nie tablicujemy). To, o czym chciałbym napisać dzisiaj, jest kwestią bardzo podobną, ale możliwą do stosowania w sytuacji spotykanej przez właściwie każdego programistę.

Chodzi o znajdowanie największego i najmniejszego elementu w dowolnej kolekcji. Uzyskanie każdej z tych wartości osobno jest proste niczym Hello world, nawet jeśli nasz język nie ma od tego żadnej wbudowanej funkcji (są jeszcze takie?). Okazuje się jednak, że oddzielne szukanie minimum i maksimum jest nieefektywne. Jeśli bowiem potrzebujemy obu wartości, to należy szukać ich jednocześnie.
Jak? Całkiem prosto. Przechodząc po zawartości pojemnika, trzeba zajmować się naraz nie jednym, lecz dwoma elementami. Zaczynamy jednak od porównania ich ze sobą, a dopiero potem z aktualnym maksimum (większy z dwóch) i aktualnym minimum (mniejszy). Implementacja tego pomysłu dla pojemników STL może wyglądać na przykład tak:
template void minmax(const C& c, T* min, T* max)
{
typename C::size_type s = c.size();
if (s == 0) return;
if (s == 1) { *min = *max = c[0]; return; }

// inicjalizacja wartości początkowych min i max
T m, M;
typename C::size_type i;
if (s & 1u) { m = M = c[0]; i = 1; }
else
{
if (c[0] <= c[1]) { m = c[0]; M = c[1]; } else { m = c[1]; M = c[0]; } i = 2; } T x, y; /* x >= y */
for ( ; i < s; i += 2) { if (c[i] <= c[i + 1]) { y = c[i]; x = c[i + 1]; } else { x = c[i]; y = c[i + 1]; } if (x > M) M = x; if (y < m) m = y; } *min = m; *max = M; }[/cpp] Ponieważ liczba elementów może być nieparzysta lub parzysta, konieczna jest odpowiednia inicjalizacja. W pierwszym przypadku bierzemy pierwszy element jako początkowe maksimum i minimum, zaś w drugim dokonujemy porównania dwóch pierwszych elementów. Resztę kolekcji możemy już przetwarzać dwójkami. Zysk wydajnościowy z takiego podejścia to teoretycznie około 25%. Wynika to z faktu, iż na dwa elementy "zużywamy" tutaj tylko trzy porównania, czyli o jedno mniej niż dla oddzielnych wywołań min i max. W praktyce osiągi te psuje bardziej czasochłonny start funkcji, więc opłaca się ją stosować głównie dla większych zbiorów elementów.

position w CSS

Niniejsza notka ma specyficzne przeznaczenie. Chociaż nie zdziwiłbym się, gdyby dla wielu osób okazała się interesująca i przydatna, to jej głównym celem jest przechowanie dla mnie pewnej wiedzy, której ogarnięcie zajęło mi całkiem sporo czasu. Tak, chodzi właśnie o tytułowy atrybut position z CSS i jego działanie.

A zatem… Jak nazwa jednoznacznie sugeruje, atrybut ten ma dużo wspólnego z określaniem umiejscowienia elementu wyświetlanego dokumentu. Nie zawiera on jednak pozycji jako takiej, lecz sposób jej wyznaczania. Jest to więc atrybut wyliczeniowy, którego możliwe wartości są następujące:

• static – domyślny sposób pozycjonowania. Element zostanie umieszczony i będzie wyświetlany w miejscu, które wynika z położenia jego znacznika w źródle dokumentu, czyli w ciągu otaczającego go tekstu. (Jeśli oczywiście sam ten tekst nie został jakoś fikuśnie wypozycjonowany). Atrybuty określające współrzędne (left, top, itd.) są ignorowane.
• relative – bardzo podobne do powyższego. Różnica polega na tym, że tutaj wspomniane atrybuty są wykorzystywane i mają wpływ na to, gdzie element jest wyświetlany. Ich punktem odniesienia jest “normalna” pozycja elementu w ciągu tekstu. Znanym przykładem są “wciskane” linki, polegające na przesunięciu łącza odrobinę w prawo i w dół, by dać wrażenie jego wciśnięcia:
  1. a:active {
  2.     position: relative;
  3.     left: 2px;
  4.     top: 2px;
  5. }

  To, czego position:relative nie robi, to rzeczywista zmiana położenia elementu. Nawet jeśli jest on wyświetlany gdzie indziej, tekst będzie nadal łamany według jego normalnego położenia – tak samo jak przy position:static.

• absolute – tzw. pozycjonowanie absolutne, które w rzeczywistości jest… względne. (Ah, ta logika webdesignu ;>). Przy tym ustawieniu element jest mianowicie wyjęty z normalnego ciągu tekstu, co czasem określa się jako stworzenie nowej warstwy (layer). Jego pozycja jest wówczas określana (atrybutami left itd.) względem elementu go zawierającego, którym to jest najbliższy element nadrzędny o pozycjonowaniu innym niż static… Proste i nieskomplikowane, prawda? ;-)
• fixed – stała pozycja. Stałość polega na tym, że element nie zmienia swojego położenia podczas przewijania strony, bo punktem odniesienia jest dla niego okno przeglądarki. Tak jak w przypadku absolute, tutaj również tworzy on warstwę wyjęta z normalnego ciągu tekstu.

Tyle teoria. W praktyce mamy kilka typowych przypadków użycia. Prawdopodobnie najbardziej skomplikowanym z nich jest zastosowanie position:absolute ze względu na jego dziwne wymaganie odnośnie elementu zawierającego. Jeśli go nie uszanujemy, wówczas nasz ‘absolutnie’ wypozycjonowany element jako punkt odniesienia przyjmie cały obszar dokumentu, czyli element <body>. Aby temu zapobiec, należy otaczającemu go pojemnikowi ustawić position na relative:

Wizualnie nic on się wtedy nie zmieni (jeśli sam nie zawiera atrybutów w stylu left, itp.), natomiast będzie on mógł być kontenerem dla elementów z position:absolute.

Udekorowane funkcje

Kilkanaście dni temu opisywałem błąd, który – jak się okazało – był efektem ubocznym pewnej cechy języka Python, uznanej przeze mnie za niemal zupełnie niepotrzebną. Dla równowagi więc dzisiaj przedstawię feature, który wydaje się być bardzo przydatny – żeby nie było, że potrafię tylko krytykować ;-)

Prawdopodobnie najlepiej jest pokazać go na prostym, acz obrazowym przykładzie. Miejmy pewną funkcję na tyle dla nas istotną, że chcemy logować wszystkie jej wywołania. Wydaje się, że nic prostszego:

Ciężko jednak nazwać takie rozwiązanie uniwersalnym. Nie chodzi tu jedynie o jawnie wpisaną nazwę funkcji, ale raczej o konieczność dodawania logging.debug(...) na początku każdej funkcji, jaką chcemy monitorować. Sprawa komplikuje się jeszcze bardziej, gdy interesują nas też wyjścia z funkcji; wówczas jedynym wyjściem jest chyba opakowanie całej treści w jeden wielki blok try–finally. Rezultat na pewno nie będzie piękny :)

I tutaj właśnie z pomocą przychodzą dekoratory – ciekawa opcja języka Python, na pierwszy rzut oka przypominająca adnotacje z Javy. Podobieństwo jest jednak głównie składniowe. Udekorowana wersja naszej ważnej funkcji wygląda bowiem tak:

Znak @ poprzedza tutaj nazwę dekoratora, czyli trace (ang. śledź – i bynajmniej nie chodzi o rybę ;]). Czym jednak jest ów dekorator? Otóż on sam również jest funkcją, mogącą wyglądać choćby tak:

Jej jedynym argumentem jest w założeniu funkcja, zaś rezultatem wywołania jest… również funkcja :) A zatem nasz dekorator potrafi przekształcić jedną funkcję w drugą, a dokładniej w jej udekorowaną, “opakowaną” wersję. To opakowanie definiowane jest wewnątrz dekoratora i polega, jak widać, na poprzedzeniu wywołania oryginalnej funkcji zapisem do loga.
Oczywiście za to, aby wywołanie funkcji opatrzonej dekoratorem było tak naprawdę odwołaniem do jej udekorowanej wersji odpowiada już sam język. Nie jest to zresztą skomplikowane, bo w istocie cały mechanizm jest tylko cukierkiem składniowym. Jest to jednak bardzo smaczny cukierek, który potrafi wydatnie podnieść czytelność kodu – jeśli stosuje się go właściwie.

Do czego jednak – oprócz logowania wywołań – dekoratory mogą się przydać? Ano przede wszystkim do upewniania się, że pewne konieczne warunki wstępne dla funkcji są spełnione na jej wejściu (i ewentualnie wyjściu). Może to być na przykład:

• @connected – sprawdzenie połączenia z serwerem zanim spróbujemy wymieniać z nim dane i nawiązanie go w razie potrzeby
• @authorized – określenie uprawnień wymaganych u aktualnie zalogowanego użytkownika przed wywołaniem funkcji wykonującej potencjalnie niebezpieczną operację
• @synchronized – zabezpieczenie wywołania funkcji semaforem lub sekcją krytyczną

Wspólną cechą takich dekoratorów jest to, że są one swoistymi pseudodeklaracjami, nieodległymi koncepcyjnie zbyt daleko od komentarzy w rodzaju:

Ich przewagą jest jednak rzeczywiste sprawdzanie, czy wymagania zostały spełnione – i to w sposób automatyczny i przezroczysty. Według mnie to właśnie stanowi o ich sporej przydatności.

Zabezpieczenie przed NULL-em

Defensywne programowanie wymaga, by zabezpieczać się przed różnymi niepożądanymi sytuacjami. Jedną z częstszych jest próba odwołania się do obiektu czy wartości, która nie istnieje – czyli np. dereferencja wskaźnika pustego czy użycie odwołania zawierającego null. Stąd bardzo częste ify w rodzaju:

Kiedy jednak sprawdzenie nullowatości jest tylko częścią warunku, wtedy w ruch idzie zwykle “sztuczka” z leniwą ewaluacją (lazy evaluation):

Większość języków ją dopuszcza, jako że jest ona przy okazji pewną formą optymalizacji. Jeśli bowiem pierwszy argument operatora logicznego daje informację o prawdziwości/fałszywości całego wyrażenia, nie trzeba już wyliczać drugiego.

Inną typową sytuacją jest zamiana nulla na jakąś inną wartość domyślną:

Tutaj C# oferuje specjalny operator ??, pomyślany właśnie na tego typu okazje:

Działa on dobrze z typami Nullable, czyli specyficznym rodzajem typów pochodnych, które dopuszczają wartość null tam, gdzie typ macierzysty jej nie przewiduje:

Operator ?? przydaje się wtedy do konwersji na typ bazowy z określoną wartością domyślną.

Cebulowy postęp

Co pewien czas można natknąć się na porównania odnośnie mocy obliczeniowej komputerów bardzo dawnych i tych dzisiejszych. Takim dość typowym, często powtarzanym stwierdzeniem jest na przykład to, iż komputer sterujący misją Apollo 11 miał moc porównywalną z dzisiejszym kalkulatorem. Podobne ciekawostki służą czasami ukazaniu gigantycznego postępu, jaki dokonał się w ciągu ostatnich kilku dekad jeśli chodzi o sprawność jednostek obliczeniowych.

Interfejs komputera sterującego
Apollo 11

Jednak nierzadko służą one także kwestionowaniu kierunku zmian w szeroko pojętej technologii komputerowej, które były możliwe właśnie dzięki tak wielkiemu wzrostowi mocy obliczeniowej procesorów. Bez zbędnych słów można te argumenty streścić w postaci następującego pytania: Skoro 40 lat temu “kalkulator” o częstotliwości 1 Mhz mógł dowieźć ludzi na Księżyc, to dlaczego obecnie potrzebujemy tysiąc razy większej mocy obliczeniowej, aby napisać prosty dokument tekstowy?… Aż chciałoby się dodać: co poszło nie tak? :) Ale spokojnie, wszystko jest w jak najlepszym porządku. Takie postawienie sprawy to bowiem nic innego, jak chwytliwy slogan, który przedstawia ją w sposób zdecydowanie zbyt uproszczony. Krótko mówiąc, zionie on przerażającą ignorancją.

Nie chodzi tu już nawet o wyraźne przecenienie stopnia skomplikowania zadań, przed jakimi ów sławetny komputer pokładowy stawał i jakości rozwiązań, które dla nich znajdował (ich częścią był chociażby “interfejs użytkownika”, składający się z komunikatów-liczb, których odcyfrowanie wymagało sporej książki). Bardziej irytuje mnie sugestia, że w dzisiejszych aplikacjach cała ta olbrzymia moc obliczeniowa jest marnowana na parę w gwizdek. No, czyli właściwie na co?… Odpowiedź brzmi: na mnóstwo “oczywistych” rzeczy, na które normalnie nie zwracamy uwagi albo o których nie musimy nawet myśleć. Jest ich dużo, bardzo dużo – i ich lista cały czas się powiększa.

Przykłady? Ależ proszę; nie trzeba ich wcale daleko szukać. Czy ktoś może chociażby uczciwie powiedzieć, że dokładnie wie, jak działa Internet? Jak to się dzieje, że dane mogą zostać przesłane z jednego końca świata na drugi, mijając po drodze kilometry kabli, setki routerów, dziesiątki różnie skonfigurowanych podsieci, a pewnie i kilka satelitów, i być odczytane na komputerze nie tylko działającym pod kontrolą całkiem innego systemu operacyjnego, ale składającym się być może z zupełnie różnych podzespołów?… Totalna magia :)
Ale to jest właśnie ów gwizdek. Taka karkołomna operacja jest możliwa tylko dlatego, że występujące po drodze ogniwa dysponują wystarczającą mocą obliczeniową i przepustowością łączy, by w rozsądnym czasie dokonać wielokrotnego rozpakowywania i ponownego pakowania danych w poszczególne warstwy komunikacji. Każda z nich: Ethernet, IP, TCP, HTTP (a na tym pewnie Unicode, XML/JSON/itp., RPC i w końcu protokół własny aplikacji) służą temu, aby – paradoksalnie – coś uprościć i… przyspieszyć. Tym czymś jest oczywiście tworzenie aplikacji – to, co trwa najdłużej, jest najkosztowniejsze i nie poddaje się prostemu skalowaniu tak, jak możliwości elektroniki.

Rozwój IT polega więc (w dużym stopniu) na dodawaniu kolejnych warstw abstrakcji do coraz większej cebuli. Nie jest to jednak przyczyna, a skutek coraz lepszych możliwości technicznych sprzętu. Możemy sobie po prostu na to pozwolić. I bardzo dobrze.
Nie zapominajmy bowiem, że komputer Apollo 11 programowany był w archaicznym asemblerze przez ładnych kilka lat przez sztab wybitnych fachowców z NASA. Czy nie powinniśmy doceniać faktu, że program wykonujące równoważnie skomplikowane zadania może dzisiaj stworzyć niemal każdy w znacznie krótszym czasie i o wiele przyjemniejszy sposób? Jeśli ktoś twierdzi, że to nie jest postęp, to doprawdy nie wiem, co mu odpowiedzieć :P

Zamiast klawisza F7

Kompilacja – rozumiana w najszerszym sensie “budowania” wynikowej aplikacji – to najwyraźniej całkiem serious business. Używając wyłącznie jednego IDE (zwłaszcza gdy jest nim Visual Studio), można długo nie zdawać sobie z tego sprawy. W końcu jedną z funkcji środowisk programistycznych jest właśnie maksymalne uproszczenie tego procesu. Idealnie ze strony użytkownika wymagane jest tylko wydanie polecenia zbudowania projektu, a czasem – w przypadku budowania w tle – nawet i to nie jest potrzebne.
Nie zawsze jednak tak było i także obecnie nie zawsze proces kompilacji programu może być czymś, co uważamy za automatycznie załatwione. Wiedzą o tym zwłaszcza aktywni uczestnicy projektów open source, a szczególnie tych pisanych w językach bez jedynie słusznych IDE czy kompilatorów – takich jak C, C++ czy Java. Nic dziwnego, że właśnie z ich otoczenia wywodzą się systemy zautomatyzowanego budowania projektów.

Starym, wysłużonym i trochę już niedzisiejszym, ale wciąż szeroko używanym jest GNU Make. To z niego prawdopodobnie wywodzą się takie podstawowe koncepcje automatycznej kompilacji jak choćby target, czyli rodzaju “punktu wejścia” całego procesu. Dwa polecenia typowo służące zainstalowaniu programu ze źródeł na systemach linuksowych:

to właśnie wywołania GNU Make dla dwóch różnych targetów: domyślnego (uruchamiającego kompilację) i install (wykonującego inne czynności instalacyjne). Między targetami występują acykliczne zależności, określające wymaganą kolejność przeprowadzania poszczególnych kroków procesu budowy, a także pozwalające na pominięcie tych, które nie są aktualnie potrzebne. Dla przykładu, domyślny target może zajmować się linkowaniem, więc do działania wymagać skompilowanych modułów. Zależeć wtedy będzie od targetów, które zajmują się właśnie kompilacją. Przy dobrze napisanym pliku makefile wykonają się jedynie te odnoszące się do plików z kodem, w których faktycznie nastąpiły zmiany od czasu ostatniej budowy projektu.

Ponieważ zarówno składnia, jak i możliwości GNU Make (ograniczające się głównie do uruchamiania poleceń powłoki) pozostawiają wiele do życzenia, pojawiły się w końcu inne tego typu narzędzia. Potrzebowała ich głównie wieloplatformowa Java i stąd wziął się Apache Ant (skrót od Another Neat Tool). Nie straszy on już składnią opartą na tabulatorach; zamiast tego straszy XML-em ;-) Mimo większej przenośności międzysystemowej (abstrakcja operacji na plikach i katalogach) nadal brakuje mu jednak uniwersalności językowej, która zresztą nie wydaje się wcale celem istnienia Anta. Pomimo wyraźnego zorientowania na Javę da się go jednak z powodzeniem używać w projektach pisanych również w innych językach.

Te dwa rozwiązania to oczywiście nie jedyne systemy automatycznego budowania, z którymi możemy się spotkać. Z innych ciekawe są chociażby CMake czy Apache Maven. Warto się z nimi zapoznać, by na widok paczki, która oprócz kodu zawiera tylko plik build.xml lub makefile nie wpadać w popłoch :)

Androidowa biblioteka do screenów

Prezentuję dzisiaj napisaną przez siebie bibliotekę, służącą do wykonywania zrzutów ekranowych (screenshotów) z urządzeń pracujących pod kontrolą platformy Android. Jej zaletą jest to, że może być używana na dowolnych telefonach dzięki pewnemu sprytnemu “hackowi”, ale wymaga uprzedniego podłączenia urządzenia do komputera i użycia narzędzi dołączonych do Android SDK.

Jeśli ktoś zajmuje się pisaniem aplikacji na platformę Android, to zapraszam do testowania. Biblioteka dostępna jest jako projekt w Google Code. Enjoy :)