Archive for Programming

Prezentacja o C2DM

2011-11-04 20:21

Zamieszczam slajdy z prezentacji, którą wygłosiłem dzisiaj w ramach Polidea Talks. Dotyczy ona androidowego wynalazku znanego jako Cloud to Device Messaging (C2DM) i będącego odpowiednikiem apple’owych Push Notifications z systemów iOS i OSX. Dla nie do końca zorientowanych spieszę z wyjaśnieniem, iż jest po prostu dość sprytny sposób na to, by urządzenie mobilne mogło “natychmiast” otrzymywać informacje ze zdalnego serwera – bez konieczności regularnej synchronizacji, która zużywa baterię i nie tylko.

File: Push! - Instant notifications on Android through C2DM  Push! - Instant notifications on Android through C2DM (591.7 KiB, 1,127 downloads)

Slajdy są tym razem w klasycznym PDF-ie. Chwilowo nie mam żadnej lepszej alternatywy dla starego, dobrego PowerPointa :)

Kod ci wszystko wytłumaczy

2011-10-27 22:12

(…) są dwa style pisania – pierwszy to: “popatrzcie jaki ja jestem mądry” – a drugi to: “popatrzcie jakie to proste”.

Jerzy Grębosz, Symfonia C++

Autor tego stwierdzenia miał na myśli przede wszystkim pisanie technicznej prozy, a więc wszelkiego rodzaju artykułów, książek, kursów i tutoriali (i blogów? ;]). Po namyśle stwierdzam jednak, że równie dobrze nadaje się ono i do poezji – czyli kodu. Podobnie bowiem przedstawia się kwestia wyższości drugiego stylu nad pierwszym, w większości przypadków.

“Większość” nie oznacza aczkolwiek “wszystkich”. Czasami górę biorą na przykład kwestie wydajnościowe, które niekiedy uzasadniają wyprodukowanie kodu wyglądającego jak przemyślnie zaszyfrowane zaklęcie. Klasycznym przykładem jest procedura szybkiego obliczania 1/\sqrt{x}, wyciągnięta wprost ze źródeł Quake‘a III:

  1. float InvSqrt (float x){
  2.     float xhalf = 0.5f*x;
  3.     int i = *(int*)&x;
  4.     i = 0x5f3759df - (i>>1);
  5.     x = *(float*)&i;
  6.     x = x*(1.5f - xhalf*x*x);
  7.     return x;
  8. }

Funkcja ta (której autorstwo niesłusznie przypisuje się czasem Johnowi Carmackowi) doskonale pokazuje, jak ważna jest czytelność i zrozumiałość kodu. Robi to w najlepszy możliwy sposób, tj. nie posiadając żadnej z tych dwóch cech :) W zamian oferuje znacznie ważniejszą w swoim zastosowaniu jakość – czyli wydajność.
Obliczanie odwrotności pierwiastka kwadratowego to jedna z najczęściej używanych operacji w grafice 3D – zawiera ją np. każda normalizacja wektora. Sensowne jest więc jak największe zoptymalizowanie tej funkcji. Będzie ona przecież wywoływana setki czy tysiące razy podczas renderowania pojedynczej klatki.

W sumie daje to kilkadziesiąt tysięcy wywołań na sekundę, a to dość unikatowa perspektywa jeśli chodzi o wartościowanie szybkości, czytelności, elastyczności – i tak dalej. I właśnie dlatego wspominam o niej jako o oczywistym wyjątku. Parafrazując popularną ostatnio proporcję: w 99% przypadków podobny kompromis nie będzie musiał dotyczyć nawet 1% kodu :)

O wiele bardziej typową sytuacją jest bowiem zdecydowana wyższość klarowności, czystości i zrozumiałości. To jest właśnie ów drugi styl: “zobaczcie jakie to proste”. Bierze on pod uwagę oczywisty w gruncie rzeczy fakt, iż głównym odbiorcą kodu jest człowiek, a nie komputer. Jeśli przyszły czytelnik potrafi z łatwością zrozumieć intencje autora – bo są one wyrażone przejrzyście i jednoznacznie – to niemal równie łatwo przyjdzie mu modyfikacja, rozszerzanie i poprawianie programu. Nie wspominając już nawet o tym, że program, który daje się łatwo “wytłumaczyć” samym kodem z definicji nie może być zanadto skomplikowany. Syntaktyczna prostota przekłada się więc na semantyczną, która z kolei dobrze koreluje z innymi pożądanymi właściwościami – jak choćby niezawodnością.

Proste haszowanie obiektów

2011-10-15 19:37

W językach wspierających obiektowość zwykle mamy do czynienia z uniwersalną klasą bazową (Object), od której wszystkie inne muszą dziedziczyć. Składniki tej klasy są więc wspólne dla wszystkich obiektów. Czasami ma to negatywne skutki (vide wait i notify w Javie), ale zazwyczaj jest przydatne, bo wspólne składniki – takie jak toString – są często niezwykle użyteczne.
Istnieje jednak pewna metoda bazowa obiektów, której przeznaczenie nie musi być od razu oczywiste. Nazywa się ona dość podobnie w różnych językach: GetHashCode w C#, hashCode w Javie, zaś w Pythonie jest to po prostu __hash__. Nietrudno się więc domyślić, że ma ona coś wspólnego z hashem obiektu :) O co jednak dokładnie chodzi?

Hash to kompaktowa reprezentacja pewnej porcji danych, uzyskana za pomocą określonego algorytmu. Takim algorytmem może być na przykład MD5, SHA1, SHA256 i inne. Podstawowym wymaganiem, jakie stawia się takim funkcjom, jest determinizm: dla identycznych danych powinny one zwracać dokładnie te same wyniki.
Do czego jednak przydaje się możliwość haszowania< dowolnych obiektów? Otóż pozwala to na tworzenie kontenerów haszujących, takich jak zbiory i mapy. W Javie na przykład chodzi tu o pojemniki HashSet i HashMap, będące jednymi z możliwych implementacji ogólnych interfejsów Set i Map. Takie kontenery używają hashy jako podstawy swojego działania, zakładając, że ich porównywanie jest szybsze niż branie pod uwagę całych obiektów. Dopiero równość ich hashy pociąga za sobą konieczność porównania samych obiektów.

Być może nasuwa się tu od razu słuszny wniosek, że hashe dla obiektów potrzebne są wobec tego jedynie wtedy, gdy implementujemy własny sposób ich porównywania. (Opisywałem kiedyś, jak to się robi w języku C#). Często powinniśmy wtedy zapewnić taką implementację ekwiwalentu metody hashCode, która będzie spójna ze sposobem porównywania. Z grubsza chodzi o to, aby na hash wpływały pola, które bierzemy pod uwagę w metodzie equals/Equals/__eq__ – i tylko one.

W jaki sposób miałyby jednak to robić? No cóż, w teorii możemy zaprząc do pracy wymienione wyżej algorytmy i potraktować nimi połączone wartości pól obiektu (albo po prostu kawałek pamięci, w którym on rezyduje). W praktyce to bardzo kiepskie rozwiązanie (zwłaszcza wydajnościowo), bowiem wspomniane funkcje haszujące niezupełnie do tego służą. Istnieje bowiem różnica między kryptograficzną funkcją haszującą a zwykłą: ta pierwsza ma na celu przede wszystkim uniemożliwienie odtworzenia oryginalnych danych, jeśli znany jest tylko ich hash. W przypadku funkcji używanych wraz z pojemnikami haszującymi bardziej interesuje nas jednorodność, co (w uproszczeniu) oznacza, że hash obiektu powinien być wrażliwy na wartości poszczególnych pól tego obiektu. Z tego też powodu poniższe rozwiązanie:

  1. @Override
  2. public int hashCode() {
  3.     return 42;
  4. }

jest do niczego, mimo że świetnie spełnia teoretyczne wymaganie, aby dwa równe obiekty miały równe hashe.

Dostępna jest oczywiście wyrafinowana wiedza na temat konstruowania dobrych (a nawet doskonałych) funkcji haszujących, ale dokładnie rachunki prawdopodobieństwa kolizji nieczęsto nas interesują – zwłaszcza, jeśli właściwie nie wiemy, w jakich pojemnikach i wśród jakich innych obiektów skończą te nasze. Na szczęście mamy też prostsze warianty. Wśród nich interesująco wygląda na przykład sposób pokazany w znanej książce Effective Java, który wygląda mniej więcej w ten sposób:

  1. Zaczynamy od dowolnej liczby dodatniej.
  2. Dla każdego znaczącego pola w obiekcie:
    1. bierzemy jego 32-bitową reprezentację (w razie potrzeby używając operacji bitowej xor dla większych pól)
    2. dodajemy ją do wyniku, uprzednio pomnożonego przez małą liczbę pierwszą

Zastosowanie go np. do prostej klasy punktu 3D wyglądałoby na przykład tak:

  1. public class Point3D {
  2.     private float x, y, z;
  3.     // ...
  4.     @Override public int hashCode() {
  5.         int res = 23;
  6.         res = 31 * res + Float.floatToIntBits(x);
  7.         res = 31 * res + Float.floatToIntBits(y);
  8.         res = 31 * res + Float.floatToIntBits(z);
  9.         return res;
  10.     }
  11. }

Wybór 23 jest raczej arbitralny, natomiast 31 ma tę zaletę, że mnożenie przez nią liczby x jest równoważne przesunięciu bitowemu i odejmowaniu, tj. (x << 5) - x. Analogicznie jest zresztą dla innych liczb o jeden mniejszych od potęg dwójki.

Tags: , , ,
Author: Xion, posted under Programming » Comments Off on Proste haszowanie obiektów

Niekoniecznie długie nazwy

2011-10-09 23:22

Porzekadło głosi, że w informatyce są tylko dwa trudne problemy: nazewnictwo, mechanizmy cache‘owania i pomyłki o jedynkę. Jeśli chodzi o jeden dwa ostatnie, to może przyjrzymy się im przy innej okazji… Dzisiaj chciałbym za to zająć się pierwszym z nich: dobieraniem odpowiednich nazw dla konstrukcji programistycznych, takich jak funkcje czy klasy.

Nie każda nazwa jest właściwa. O tej trywialnej prawdzie każdy pewnie przekonał się już dawno, zwłaszcza jeśli przechodził przez fazę zmiennych a, b, c lub funkcji fun1 i fun2. Zdaje się zresztą, że kiedyś była to powszechna przypadłość, co widać zwłaszcza w przypadku starych API *niksowych. Najwyraźniej jednak poszliśmy kolektywnie po rozum do głowy i dziś już nikt nie nazwie funkcji wait3 czy wait4.

Nietrudno jest oczywiście wskazać podstawowy problem tego rodzaju nazw. Jakkolwiek jest on ściśle związany z długością, nie uzasadnia to automatycznie stwierdzenia, że wszystkie krótkie nazwy są złe. Żeby nie odchodzić daleko, wystarczy tylko spojrzeć na POSIX-owe, uniwersalne funkcje read i write. Ich nazwom nie brakuje dokładnie niczego; przeciwnie, próba dodania czegoś więcej wprowadzałaby tylko zamieszanie. readFromFileDescriptor może i wskazywałaby wyraźnie na źródło danych, ale czy zupełnie poprawne użycie takiej funkcji na uchwycie sieciowego gniazda (socket) nie byłoby mylące? O jakim pliku wtedy mówimy?
Naturalnie, w *niksach “wszystko jest plikiem” i należy o tym wiedzieć. Lecz skoro tak jest, to co zyskujemy przez dłuższą nazwę funkcji read? Niby z czego innego niż z pliku mielibyśmy czytać?…

Dywagując na ten temat muszę koniecznie zaznaczyć, że nazwy zaśmiecone oczywistymi informacjami nie są wcale hipotetycznym problemem. Moim ulubionym przykładem – ze względu na swoją groteskową wręcz ekstremalność – jest poniższe wywołanie:

  1. NSString* someString = @"Ala ma kota";
  2. NSString* otherString = [someString
  3.                          stringByReplacingOccurrencesOfString:@"kota"
  4.                          withString:@"psa"];

Ja wcale nie żartuję – tak w Objective-C (OSX/iOS) wygląda zastępowanie jednego ciągu w tekście innym. Zawsze chętnie wysłucham argumentów przekonujących o ekspresywności i opisowości podobnych nazw, ale nigdy nie uwierzę, że koderzy je rzeczywiście czytają. Zgaduję, że ich percepcja u statystycznego programisty polega na dostrzeżeniu “Repl” lewym okiem i “ccurr” prawym – albo coś w tym rodzaju. Jeśli mam rację, to nazwa ta jest znacząca w zaledwie 22 procentach; trudno to uznać za dobry stosunek sygnału do szumu.

Czy można było zrobić to lepiej? Zapewne – weźmy chociażby Javę:

  1. String someString = "Ala ma kota";
  2. String otherString = someString.replaceAll("kota", "psa");

Wygląda to całkiem dobrze. Okazuje się, że można użyć trzy razy krótszej nazwy i osiągnąć niemalże ten sam efekt, posługując się po prostu samą składnią języka (kolejnością parametrów i wartością zwracaną) zamiast długich tekstowych opisów.

Rozwlekłe nazwy – nawet jeśli camelCase czyni je znośnymi – nie zawsze są więc dobrą odpowiedzią. Czasami mogą one być równie nadmiarowe co niepotrzebne komentarze.

Tags: , , ,
Author: Xion, posted under Programming » 6 comments

Trzy rodzaje metod w Pythonie

2011-10-03 23:05

Obiekty mają metody. Tak, w tym stwierdzeniu nie należy doszukiwać głębokiego sensu – jest ono po prostu prawdziwe :) Gdy mówimy o metodach obiektów czy też klas, zwykle mamy jednak na myśli tylko jeden ich rodzaj: metody instancyjne. W wielu językach programowania nie jest to aczkolwiek ich jedyny rodzaj – z takim przypadkiem mamy do czynienia chociażby w Pythonie.

Jak zawsze metody instancyjne są domyślnym typem, który tutaj jest dodatkowo zaznaczony obecnością specjalnego parametru – self – występującego zawsze jako pierwszy argument. To odpowiednik this z języków C++, C# czy Java i reprezentuje instancję obiektu, na rzecz której wywoływana jest metoda:

  1. class Counter(object):
  2.     def __init__(self, value = 0):
  3.         self._value = value
  4.     def increment(self, by = 1):
  5.         self._value += by

Fakt, że musi być on jawnie przekazany, wynika z zasad tworzenia zmiennych w Pythonie. Nie muszą być one jawnie deklarowane. Dlatego też odwołanie do pola obiektu jest zawsze kwalifikowane, gdyż przypisanie do _value zamiast self._value stworzyłoby po prostu zmienną lokalną.

Istnieją jednak takie metody, które nie operują na konkretnej instancji klasy. Typowo nazywa się je statycznymi. W Pythonie nie posiadają one parametru self, lecz są opatrzone dekoratorem @staticmethod:

  1. @staticmethod
  2. def format_string():
  3.     return "%d"

Statyczną metodę można wywołać zarówno przy pomocy nazwy klasy (Counter.format_string()), jak i jej obiektu (Counter().format_string()), ale w obu przypadkach rezultat będzie ten sam. Technicznie jest to bowiem zwyczajna funkcja umieszczona po prostu w zasięgu klasy zamiast zasięgu globalnego.

Mamy wreszcie trzeci typ, mieszczący się w pewnym sensie pomiędzy dwoma opisanymi powyżej. Nie wydaje mi się jednak, żeby występował on w żadnym innym, popularnym języku. Chodzi o metody klasowe (class methods). Nazywają się tak, bo są wywoływane na rzecz całej klasy (a nie jakiejś jej instancji) i przyjmują ową klasę jako swój pierwszy parametr. (Argument ten jest często nazywany cls, ale jest to o wiele słabsza konwencja niż ta dotycząca self).
W celu odróżnienia od innych rodzajów, metody klasowe oznaczone są dekoratorem @classmethod:

  1. @classmethod
  2. def from_other(cls, counter):
  3.     return cls(counter._value)

Podobnie jak metody statyczne, można je wywoływać na dwa sposoby – przy pomocy klasy lub obiektu – ale w obu przypadkach do cls trafi wyłącznie klasa. Tutaj akurat będzie to Counter, lecz w ogólności może to być także klasa pochodna:

  1. class BoundedCounter(Counter):
  2.     MAX = 100
  3.  
  4.     def __init__(self, value = 0):
  5.         if value > self.MAX:
  6.             raise ValueError, "Initial value cannot exceed maximum"
  7.         super(BoundedCounter, self).__init__(value)
  8.  
  9.     def increment(self, by = 1):
  10.         super(BoundedCounter, self).increment(by)
  11.         self._value = min(self._value, self.MAX)
  12.  
  13.     @classmethod
  14.     def from_other(cls, counter):
  15.         value = min(counter._value, cls.MAX)
  16.         return cls(value)

Powyższy kod – będący przykładem dodatkowego sposobu inicjalizacji obiektu – to dość typowy przypadek użycia metod klasowych. Korzystanie z nich wymaga aczkolwiek nieco wprawy w operowaniu pojęciami instancji klasy i samej klasy oraz ich poprawnego rozróżniania.
W gruncie rzeczy nie jest to jednak nic trudnego.

Tags: , , ,
Author: Xion, posted under Programming » 4 comments

Piękna i JavaScript

2011-09-29 22:15

Publikuję slajdy z prezentacji The Beauty and the JavaScript, którą wygłosiłem w zeszły poniedziałek w ramach Polidea Talks – cyklu wykładów wygłaszanych w różnych odstępach czasu przez osoby pracujące w Polidei. Jak sugeruje nazwa, rzecz dotyczyła języka JavaScript i bynajmniej nie przedstawiała go w specjalnie pozytywnym świetle ;) Chciałem aczkolwiek pokazać, że przy odrobinie dobrej woli i zręcznym unikaniu pułapek da się z nim żyć, co obecnie jest często koniecznością.

File: The Beauty and the JavaScript  The Beauty and the JavaScript (27.6 KiB, 847 downloads)

Sama prezentacja jest też pewnego rodzaju ciekawostką, bo została przygotowana jako dokument HTML do oglądania w przeglądarce WWW. Do renderowania slajdów używa biblioteki S5, która napisana została w – a jakże – JavaScripcie. Rozwiązanie to sprawdziło się zresztą całkiem nieźle w przypadku prostych slajdów, takich jak niniejsze.

Całość jest też dostępna jako gałąź w repozytorium na GitHubie.

Tags: , ,
Author: Xion, posted under Events, Programming » 5 comments

pyduck – biblioteka do interfejsów w Pythonie

2011-09-26 22:16

Czas pochwalić się swoim nowym dziełem. Nie jest ono bardzo imponujące ani specjalnie duże. Mam jednak nadzieję, że będzie ono przydatne dla tego (wąskiego) grona odbiorców, do którego jest skierowane.

Mam tu na myśli niewielką biblioteką do Pythona, która ma na celu poprawienie użyteczności jednej z głównych, ideowych cech języka – tak zwanego typowania kaczkowego (duck typing). Geneza tego terminu jest oczywiście wielce intrygująca, ale założenie jest proste. Zamiast czynić obietnice i jawnie deklarować implementowane interfejsy, obiekty w Pythonie “po prostu są” i zwykle próbują być od razu używane do założonych celów. Jeśli okażą się niekompatybilne (np. nie posiadają żądanej metody), wtedy oczywiście rzucany jest wyjątek. Pythonowska praktyka polega więc na przechodzeniu do rzeczy bez zbędnych ceregieli i obsłudze ewentualnych błędów.

Ma to rzecz jasna swoje zalety, ma też wady, a czasami może również rodzić problemy, jeśli błąd spowodowany niekompatybilnością obiektu ujawni się za późno. Z drugiej strony brak konieczności jawnego specyfikowania implementowanych interfejsów to spora zaleta. Najlepiej więc byłoby jakoś połączyć te dwa światy i umożliwić wcześniejsze sprawdzenie możliwości obiektu…

Jak można się pewnie domyślić, to właśnie próbuje umożliwić mój framework, noszący wdzięczną nazwę pyduck. Dodaje on do Pythona mechanizm interfejsów bardzo podobny do tego, który obecny jest w języku Go. Najważniejszą jego cechą jest właśnie fakt, że w konkretnych typach interfejsy są implementowane niejako automatycznie – wystarczy, że mają one odpowiednie metody. Samo sprawdzenie, czy obiekt implementuje dany interfejs polega zaś na faktycznym zaglądnięciu w listę jego metod, a nie weryfikacji jakichś jawnych deklaracji.

Inaczej mówiąc, nie czynimy tutaj żadnych obietnic odnośnie obiektu, ale wciąż mamy możliwość kontroli, czy nasze wymagania są spełnione. Najlepiej ilustruje to oczywiście konkretny przykład:

  1. from pyduck import Interface, expects
  2.  
  3. class Drawable(Interface):
  4.     def get_bounds(self): pass
  5.     def draw(self, canvas): pass
  6.  
  7. class Canvas(object):
  8.     @expects(Drawable)
  9.     def draw_object(self, obj):
  10.         bounds = obj.get_bounds()
  11.         self.set_clipping_bounds(bounds)
  12.         obj.draw(self)

Zaznaczamy w nim, że metoda Canvas.draw_object spodziewa się obiektu zgodnego z interfejsem Drawable. Jest on zdefiniowany wyżej jako posiadający metody get_bounds i draw. Sprawdzenie, czy rzeczywisty argument funkcji spełnia nasze wymogi, zostanie wykonane przez dekorator @expects. Zweryfikuje on obecność i sygnatury metod wspomnianych metod.
Dzięki temu będziemy mogli być pewni, że mamy do czynienia z obiektem, który rzeczywiście potrafi się narysować. Jego konkretna klasa nie będzie musiała natomiast nic wiedzieć na temat interfejsu Drawable ani jawnie deklarować jego wykorzystania.

Po więcej informacji zapraszam oczywiście na stronę projektu na GitHubie. Ewentualnie można też od razu zainstalować paczkę, np. poprzez easy_install:

  1. $ sudo easy_install pyduck

A ponieważ wszystko open source jest zawsze wersją rozwojową, nie muszę chyba wspominać, że z chęcią witam pull requesty z usprawnieniami i poprawkami :>

Tags: , , , ,
Author: Xion, posted under Programming » 1 comment
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.