Monthly archive for October, 2011

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ą.

Czwarty dodatek do WoW-a

2011-10-23 16:53

Nie mam już wiele wspólnego ze światkiem World of Warcraft, ale akurat wieści o nowych dodatkach potrafią jeszcze wzbudzić we mnie zainteresowanie. Tak jest też z ogłoszonym (przed)wczoraj – zależnie od strefy czasowej – dodatkiem numer cztery, noszącym nazwę Mists of Pandaria.
Z pozoru nie zaskakuje on niczym nadzwyczajnym, jako że pod względem rozszerzeń WoW stał się już podobny do The Sims: ta sama idea z nowymi dekoracjami. Mamy więc tutaj wyższy limit poziomu postaci (90), nowy kontynent (Pandaria), nową rasę i klasę, świeżą dostawę instancji i raidów – i tak dalej. Krótko mówiąc: standard. W takiej sytuacji naturalnie jest poszukiwanie rozwiązań, które nie wpadają tak łatwo w dobrze znane szuflady i pozwalają domyślać się, w jakim kierunku gra będzie dalej podążać.
A według mnie jest on dość oczywisty. Otóż Blizzard chce dokonać czegoś, co jest “niemożliwe”, a zarazem absolutnie konieczne, biorąc pod uwagę obecne trendy w komputerowej rozrywce. Wyzwanie jest koncepcyjnie aż nazbyt proste, ale jego realizacja – jeśli w ogóle możliwa – wymaga balansowania na bardzo, bardzo cienkiej linie.

Co należy zrobić? Bagatela: połączyć Diablo z FarmVille – w przenośni, rzecz jasna.

Tags:
Author: Xion, posted under Games, Thoughts » 4 comments

GDD w Pradze

2011-10-19 21:48

Miałem ostatnio okazję wzięcia udziału w jednej z lokalnych edycji konferencji Google Developer Day. Na to wydarzenie składa się cykl wykładów prowadzonych przez przedstawicieli Google, traktujących o technologiach webowych, mobilnych i tym podobnych tematach. GDD, w którym akurat ja uczestniczyłem, odbywał się wczoraj w Pradze.

Przyznam, że nigdy wcześniej nie brałem udziału w podobnym wydarzeniu, więc było to bardzo interesujące doświadczenie. Większość z prezentowanych tematów wydawała się niezwykle ciekawa, a ze względu na to równoległy przebieg aż pięciu ścieżek wykładowych należało dokonać bardzo trudnego wyboru, których sesji chcemy posłuchać. Miejmy nadzieję, że wszystkie tak czy siak wkrótce trafią na YouTube :)

Od siebie dodaję kilka zdjęć. Ich jakość nie jest aczkolwiek powalająca, bo zostały wykonane sprzętem, którego główne przeznaczenie jest zgoła odmienne ;)

Update: Oficjalna galeria zdjęć z imprezy jest już dostępna.

Tags: ,
Author: Xion, posted under Computer Science & IT, Events » 3 comments

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
 


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