Monthly archive for June, 2011

Kwitnące zbiory

2011-06-30 22:03

Przedstawię dzisiaj interesującą strukturę danych, będącą pewnego rodzaju uogólnieniem lub modyfikacją kontenerów typu bitset. Nazywa się ona filtrem Blooma (Bloom filter) i stanowi przykład struktury probabilistycznej, czyli działającej… czasami ;) Nie niweluje to aczkolwiek w żaden sposób jej przydatności, o czym zresztą opowiem dalej.

Filtr Blooma to tablica bitowa, w której przechowujemy pewien zbiór. Liczba owych bitów – i to jest pierwsza różnica w stosunku do bitsetunie jest równa liczbie wszystkich możliwych elementów zbioru. Wręcz przeciwnie, zwykle jest ona znacznie, znacznie mniejsza.
Drugą różnicą jest reprezentacja elementu, która dla odmiany zajmuje więcej miejsca. Definiuje je określona z góry liczba bitów, rozrzuconych po całej tablicy i ustawionych na 1. Sposób owego rozmieszczenia jest określony przez zestaw funkcji haszujących, przyjmujących element zbioru jako swój argument i zwracających indeks jednej z pozycji w tablicy. Owych funkcji jest zaś tyle, ile bitów reprezentacji.


Poglądowe przedstawienie filtru Blooma

Jak wyglądają operacje na tak zaimplementowanych zbiorze? Sprawdzenie przynależności jest proste, bo sprowadza się do obliczenia wartości wszystkich funkcji haszujących dla danego elementu i upewnieniu się, że na zwróconych przez nie pozycjach tablicy jest zapisana jedynka. Dodawanie, jak można się domyślić, polega na ustawieniu tychże jedynek. A co wobec tego z usuwaniem elementu?
Otóż usuwania… nie ma :) Jest to zamierzony efekt, konsekwencja założeń które czynią filtr Blooma strukturą probabilistyczną. Dopuszcza ona mianowicie fałszywe pozytywy. Są to przypadki, w których filtr odpowiada pozytywnie na pytanie o przynależność elementu, gdy w rzeczywistości element ten do zbioru nie należy. Jest to jednak jedyny rodzaj dopuszczalnych błędów. Wykluczone są w szczególności sytuacje odwrotne: gdy element jest w zbiorze, ale filtr odpowiada coś przeciwnego (byłby to z kolei fałszywy negatyw). Usuwanie – polegające na wyzerowaniu odpowiednich bitów – mogłoby jednak do dopuścić do takiej sytuacji. Wynika to z faktu, że każdy z bitów w tablicy odpowiada za przechowywanie więcej niż jednego elementu.

Przypuszczam, że wobec powyższych cech filtrów Blooma pojawiają się dwa pytania, z których jedno dotyczy częstotliwości pojawiania się fałszywych pozytywów. Zależy to oczywiście od rozmiaru tablicy (m), liczby funkcji haszujących (k), a także liczby elementów będących aktualnie w zbiorze (n). Ogólny wzór jest, jak widać, raczej nieoczywisty ;)
Dlatego pozwolę sobie raczej przejść do drugiego pytania: o zastosowania. Te są całkiem rozliczne – dotyczą chociażby przyspieszania dostępu do dużych kolekcji danych. Jeśli koszt wczytania danych odpowiadających danemu kluczowi jest spory (bo wymaga np. odczytu z dysku lub sieci), wówczas utrzymywanie w pamięci filtru Blooma może znacząco polepszyć efektywność poprzez szybkie odrzucanie zapytań o nieistniejące klucze. Oczywiście filtr będzie czasami się mylił, ale jego użycie i tak pozwoli ograniczyć liczbę drogich odwołań co najmniej o rząd wielkości.

Przykładową implementację filtru Blooma – wykorzystującą do haszowania generator liczb pseudolosowych – można zobaczyć choćby tutaj.

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

Recykling nazw w kodzie

2011-06-26 20:24

W dziedzinie optymalizacji kodu pojawia się często pojęcie aliasowania. Z grubsza polega ono na tym, że jakaś komórka pamięci (lub bardziej ogólnie: zmienna) może być dostępna pod więcej niż jedną “nazwą” czyli np. wskaźnikiem lub referencją. Taka sytuacja sprawia, że kompilator ma mniejsze pole manewru w zakresie optymalizacji dostępu do niej. Typową konsekwencją jest konieczność ponownego odczytywania wartości tej komórki zamiast posłużenia się cache‘owanym rezultatem zapisanym w jednym z rejestrów procesora.
Aliasing w większym lub mniejszym stopniu dotyczy właściwie wszystkich języków kompilowanych. Jest on jednak brany pod uwagę głównie tam, gdzie jego wpływ na wydajność jest największy, tj. w kodzie kompilowanym bezpośrednio do instrukcji maszynowych konkretnego sprzętu. Kod w C i C++ to najważniejszy przykład tego rodzaju.

Niejako na przeciwnym biegunie – zwłaszcza pod względem liczby warstw abstrakcji pod spodem – sytuują się języki interpretowane z dynamicznym typowaniem. Javascript i Python są tutaj typowymi reprezentantami. W nich problem “aliasowania” przybiera według mnie formę dokładnie odwrotną i nie dotyczy już kwestii wydajnościowych – z których wspomniane języki przecież nie słyną :) Przeciwnie: ów symetryczny problem jest związany z ich wyróżniającą zaletą: prostotą i czytelnością kodu.
O jaki więc rodzaj aliasowania chodzi? Ano taki, który polega na używaniu jednej nazwy do wielu różnych wartości. Przy czym ‘nazwę’ rozumiem tu w sensie stricte programistycznym, obejmującym także jej zasięg i uwzględniającym wszystkie dodatkowe cechy tego pojęcia – jak choćby przesłanianie (name shadowing).
Od razu zastrzegam jednak, żeby nie rozumieć tego zbyt dosłownie. W tym sensie chociażby poniższa pętla:
for (int i = 0; i < 10; ++i) { /* ... */ }[/cpp] nie stanowi odpowiedniego przykładu mimo tego, iż zmienna i jest tutaj używana do “nazwania” aż dziesięciu formalnie różnych wartości (\{0, ..., 9\}). Koncepcyjnie każda z nich jest bowiem tym samym, tj. wartością licznika pętli w danej iteracji.

Wątpliwej słuszności jest dopiero praktyka recyklingu tych samych nazw do różnych celów. Jest tu oczywiście spory margines niepewności jeśli chodzi o definicję słowa ‘różny’. Być może dla niektórych osób coś podobnego do poniższego kodu jest już po złej stronie granicy między akceptowalną a niedobrą praktyką:

  1. def strip_html(data):
  2.     ''' Strips HTML tags and stuff from given text, making it plain text. '''
  3.     data = strip_html_tags(data)
  4.     data = strip_html_entities(data)
  5.     data = normalize_whitespace(data)
  6.     return data

Inni z kolei mogą nie widzieć nic złego w użyciu jednej zmiennej (np. node) do przekopania się przez pięciokrotnie zagnieżdżoną strukturę XML-a czy JSON-a. Wypada tylko mieć nadzieję, że osoba utrzymująca potem taki kod będzie prezentowała podobny poziom wrażliwości ;-)

Nietrudno zauważyć, że wielokrotne używanie tych samych nazw do różnych celów jest zupełnie możliwe także w językach kompilowanych ze statycznym typowaniem. Dynamiczne typowanie zapewnia jednak o wiele większą “zachętę” do takich praktyk, pozwalając chociażby na takie oto smaczki:

  1. if foo: foo = foo[0] # lista -> pojedynczy obiekt
  2. foo = [foo] # pojedynczy obiekt -> lista
  3. foo = str(foo) # obiekt -> string
  4. foo = str.join(foo, " ") # lista -> string
  5. foo = ["%s=%s\n" % i for i in foo.items()] # słownik -> "klucz=wartość"

Czy mieszczą się one w kategorii prostoty i czytelności, każdy pewnie oceni indywidualnie. Nie da się jednak ukryć, że kryją one w sobie wielki potencjał zarówno upraszczania, jak i zaciemniania kodu. To wielka moc, z którą naturalnie jest związana wielka odpowiedzialność :)

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

Niekoniecznie należy słuchać ekspertów

2011-06-20 22:45

Nieodłączną częścią realizacji projektu programistycznego jest wybór używanych technologii. Dotyczy to zarówno samego początku, jak i późniejszych etapów, gdy czasami trzeba zdecydować się np. na skorzystanie z jakiejś biblioteki X lub jej zamiennika Y. Takie dylematy mają i koderzy-amatorzy (co często uzewnętrzniają na przeróżnych forach ;]), i firmy tworzące oprogramowanie komercyjnie. Decyzję trzeba jednak w końcu podjąć; czy są jakieś uniwersalne kryteria, którymi można się kierować?
Inżynieria oprogramowania każe zwykle zdać się na poprzednie doświadczenia lub wiedzę ekspertów. Ta druga opcja jest często preferowana wobec braku podstaw (tj. wspomnianych doświadczeń) do skorzystania z pierwszej. Wydaje się to rozsądne. W końcu osoba, która bardzo dobrze zna dane rozwiązanie, powinna mieć też odpowiednie pojęcie o tym, czy aplikuje się ono do konkretnego problemu.

A jednak mam co do tego całkiem poważne wątpliwości. Potrafiłbym znaleźć kilka sensownych argumentów na to, że osoba biegła w stosowaniu danej technologii nie musi być wcale dobrym doradcą. W grę mogą bowiem wchodzić silne czynniki zaburzające solidność osądu eksperta. Przychodzą mi na myśl zwłaszcza dwa:

  • Osoba świetnie znająca jakieś rozwiązanie jest z pewnością taką, która zastosowała je w co najmniej kilku projektach. Kto wie, być może nawet zakończyły się one sukcesem ;) Niezależnie od ich wyniku, zdobyte przy okazji doświadczenie prawdopodobnie nauczyło naszego eksperta, jak powinien radzić sobie z przeróżnymi kruczkami, niejasnościami, niedoróbkami, brakami czy wręcz jawnymi bugami występującymi w danej platformie czy bibliotece. Jeśli wielokrotnie i z powodzeniem dawał sobie z nimi radę, jest wielce prawdopodobne, iż będzie (nawet nieświadomie) umniejszał ich znaczenie podczas “obiektywnej” oceny całego rozwiązania. Po prostu z perspektywy czasu nie będą się one wydawały aż tak dolegliwe, jakie mogą być w rzeczywistości dla osoby słabiej obeznanej z daną technologią.
  • Nasz ekspert od rozwiązania X na pewno poświęcił sporo czasu i mocy obliczeniowej swoich neuronów na dokładnie zapoznanie się z jego szczegółami. Wysiłek ten sprawił przy okazji, że w naturalny sposób zaczął on wyżej cenić X-a, ponieważ w ten sposób potwierdzał w swoich oczach słuszność decyzji, aby rozwijać swoją znajomość tego zagadnienia. Dzięki tej (znów: zwykle nieświadomej) praktyce, nasz ekspert zapobiegł powstaniu dysonansu poznawczego (cognitive dissonance) lub przynajmniej znacząco go zredukował. Efektem ubocznym tego zjawiska jest jednak zaburzone postrzeganie wartości X-a jako rozwiązania, związane głównie z tzw. błędem potwierdzania (confirmation bias) lub zaprzeczania (disconfirmation bias). Krótko mówiąc, nasz ekspert generalnie przywiązuje większą wagę do pozytywnych ocen X-a, a mniejszą do negatywnych. Niezbyt dobrze wróży to jego obiektywności.

Jak wynika z powyższych argumentów, wypowiedziane przez eksperta zdanie na temat przydatności jakiegoś rozwiązania niekoniecznie musi być obiektywne i wartościowe. Oczywiście nie twierdzę, że największe pole do popisu przy podejmowaniu decyzji powinni mieć wobec tego początkujący, bo to z kolei zakrawa na przegięcie w drugą stronę :) Sądzę jednak, że najbardziej kompetentnymi i obiektywnymi osobami byłyby takie, które wprawdzie stosowały dane rozwiązanie w praktyce, ale nie są w nim całkiem biegłe. A już zupełnie dobrze byłoby wówczas, jeśli mają one też pewne pojęcie o porównywalnych, alternatywnych rozwiązaniach.

Podstawy autouzupełniania

2011-06-16 22:45

Część bywalców kanału #warsztat może wiedzieć, że od jakiegoś czasu w wolnych chwilach rozwijam pewien niewielki projekt. Jest to prosty IRC-owy bot, który potrafi wykonywać różne predefiniowane czynności, dostępne za pomocą komend rozpoczynających się od kropki. Wśród nich mamy między innymi wysyłanie zapytań do wyszukiwarki Google, wyświetlanie skrótów artykułów z Wikipedii, przekazywanie wiadomości między użytkownikami i jeszcze kilka innych. W sumie jest ich już około kilkanaście, więc pomyślałem, że dobrym rozwiązaniem byłby wbudowany system pomocy oraz podpowiedzi opartych na “domyślaniu się”, jakie polecenie użytkownik chciał wydać.
Brzmi to może nieco zagadkowo, ale w gruncie rzeczy chodzi o zwykłe autouzupełnianie (autocompletion), do którego jesteśmy przyzwyczajeni w wielu innych miejscach – takich jak środowiska programistyczne czy choćby wyszukiwarki internetowe. Oczywiście tutaj mówimy o nawet miliardy razy mniejszej skali całego rozwiązania, ale ogólna zasada we wszystkich przypadkach jest – jak sądzę – bardzo podobna.

Cały mechanizm opiera się właściwie o jedną strukturę danych zwaną drzewem prefiksowym (prefix tree). Jest to całkiem pomysłowa konstrukcja, w której każde dopuszczalne słowo (zwane tradycyjnie w takich drzewach kluczem) wyznacza pewną ścieżkę od korzenia drzewa. Kolejne krawędzie etykietowane są tu znakami słowa.
Najważniejszą cechą drzewa prefiksowego jest jednak to, że wspomniane ścieżki mogą się nakładać, jeśli początkowe części danych słów się pokrywają. Stąd zresztą bierze się nazwa struktury, gdyż pozwala ona szybko znaleźć ciągi zaczynające się od podanego tekstu – czyli właśnie prefiksu.

O kompatybilności wprzód i jej dziwactwach

2011-06-11 15:36

Oto proste zadanie. Proszę sobie przypomnieć dowolną funkcję z dowolnej platformy/biblioteki/frameworka/itp. posiadającą przynajmniej jeden parametr, który nigdy nie został przez nas użyty w żadnym jej wywołaniu. Idealnie by było, gdyby ów argument występował na innej pozycji niż ostatnia – tak, żeby jego pominięcie wymagało podania zera, NULL-a, nulla, nila, Nila, None-a, pustego napisu/tablicy/listy lub dowolnej innej, “neutralnej” wartości.
Jeżeli udało nam się uporać z tą łamigłówką, to mam kolejną w postaci prostego pytania: dlaczego takie funkcje w ogóle istnieją? Zadając to pytanie na głos, często doczekamy się odpowiedzi, które niewiele mają wspólnego z prawdą. Bo istnieją rzadkie sytuacje, gdy ów felerny parametr jednak się przydaje. Bo nie ma innego dobrego miejsca, gdzie można by go umieścić. Bo język programowania jest kiepski i tak już musi być. Bo w sumie co to za kłopot z tym jednym nullem więcej. Bo.. bo… – i tak dalej.

W rzeczywistości prawidłową odpowiedzią jest zazwyczaj brzydkie słowo na ‘k’, czyli kompatybilność :) Pół biedy, jeśli chodzi tutaj o kompatybilność wsteczną – ona jest codziennością co bardziej złożonych aplikacji i systemów oraz wszelkich bibliotek, które mają swoją własną historię. Nie da się jej uniknąć i zwykle nawet nie warto próbować, chociaż oczywiście okresowe jej porzucanie jest w gruncie rzeczy wskazane.
Jest jednak jeszcze kompatybilność wprzód. Dziwna to idea, mająca na celu przewidywanie przyszłych wymagań wobec systemu i ułatwiająca lub wręcz umożliwiająca sprostanie im. Należy więc ona do dziedzin z pogranicza prorokowania i prognoz pogody, zatem z miejsca wydaje się cokolwiek podejrzana. Co więcej, potrafi się ona wkraść do projektu tak podstępnie i niezauważenie, że nie musi być nawet świadomie stosowana, by zostawić w nim swoje ślady. Ślady zupełnie niepożądane, o czym jednak przekonujemy się zwykle dopiero dużo później.

Mniej więcej coś takiego zdarzyło mi się ostatnio podczas tworzenia wersji androidowej swojej gry sprzed paru lat, czyli Taphoo. Sprawa dotyczy formatu niewielkich (<1 kB) plików, w którym obie wersje przechowują poszczególne etapy gry. Nie należy on w żadnym razie do przesadnie skomplikowanych, gdyż jest prostym formatem binarnym, składającym się z trzech części:

  • stałego nagłówka o rozmiarze dwóch bajtów, równego zawsze 54 4C (w ASCII są to znaki TL, będące skrótem od Taphoo Level)
  • wymiarów etapu: szerokości i wysokości, zapisanych na dwóch bajtach każda
  • właściwej planszy, której każda komórka zajmuje dokładnie jeden bajt


Format etapów w Taphoo

Oryginalnie format ten służył jedynie windowsowej wersji gry, ale nie widziałem żadnych powodów, dla których nie mógłbym użyć go także w powstającym porcie na platformę Android. Z pewnością znaczącym czynnikiem było to, że razem z pierwotną wersją gry napisałem też do niej – nie chwaląc się – bardzo dobry edytor :) Rozsądne było więc, aby przepisać kod wczytujący poziomy na Javę i włączyć go do gry w wersji androidowej.
Intuicja każe przypuszczać, że wtedy właśnie pojawiły się kłopoty. Faktycznie tak było. W związku mam jeszcze jedną, ostatnią dzisiaj zagadkę, która powinna być stosunkowo łatwa do rozwiązania na podstawie informacji podanych wcześniej. Co mianowicie jest przykładem niepotrzebnej kompatybilności wprzód w opisanym wyżej formacie i jakie problemy może to stwarzać podczas portowania?…

Terminologia rozproszonych systemów kontroli wersji

2011-06-06 19:31

W ostatnich latach rozproszone systemy kontroli wersji (w skrócie DVCS) stały się popularne, zwłaszcza w środowiskach związanych z open source. Warto je jednak znać nie tylko wtedy, gdy pracujemy nad projektami z otwartym źródłem. Jak bowiem pisałem wcześniej, mogą być one przydatne chociażby do małych jednoosobowych projektów. Ponadto bywają nierzadko używane w większych oraz mniejszych firmach. Ogólnie mamy więc duże szanse, aby prędzej lub później zetknąć się z takimi systemami.
Ten post jest adresowany przede wszystkim do osób, które nie miały wcześniej dłuższej styczności rozproszonymi systemami kontroli wersji. Ma on na celu wyjaśnienie wielu spośród tych tajemniczo brzmiących słówek, na jakie nieustannie można się natknąć, gdy pracujemy z DVCS-ami. Istnieje oczywiście szansa, że bardziej zaawansowani użytkownicy również wyciągną nowe wiadomości z lektury (albo chociaż przejrzenia) niniejszej notki. A jeśli nawet nie, to powtórzenie znanej sobie wiedzy na pewno im nie zaszkodzi ;)

Tags: , ,
Author: Xion, posted under Applications, Programming » 3 comments

Prawie jak lambda, w Javie

2011-06-02 20:52

Wiadomo powszechnie, że Java listenerami stoi i typowe jest używanie jest różnego rodzaju klas wewnętrznych, które są następnie podawane jako interfejsy do wywołań zwrotnych. W ten sposób obsługuje się różnego rodzaju zdarzenia, począwszy od interakcji użytkownika z programem aż po ważne notyfikacje pochodzące z systemu operacyjnego.
Gdy klasa zawierające takie handlery dostatecznie się rozrośnie, pojawia się oczywiście potrzeba jej zrefaktorowania i podzielenia na dwie lub większą liczbę mniejszych. W trakcie tego procesu czasami chciałoby się też wydzielić owe klasy wewnętrzne, obsługujące zdarzenia – i wtedy możemy napotkać pewien kłopot. Kłopocik właściwie ;)

Dotyczy on zależności między klasami wewnętrznymi a klasą je otaczającą. Ponieważ mówimy o niestatycznych niestatycznych klasach wewnętrznych, typowe jest odwoływanie się do składników klasy otaczającej z klasy zewnętrznej. Mówiąc bardziej po ludzku, implementacja np. zdarzenia kliknięcia przycisku może sięgać do obiektu okna/dialogu/itp., zawierającego tenże przycisk:

  1. private final OnClickListener buttonsListener = new View.OnClickListener() {
  2.     @Override
  3.     public void onClick(View v) {
  4.         if (v.getId() == R.id.exit_button) finish();
  5.     }
  6. }

Przeniesienie całej powyższej klasy w inne miejsce nastręcza wówczas problem, gdyż odwołuje się ona do metody klasy ją otaczającej (czyli finish()). Należałoby więc posiadać obiekt tej klasy, zapewnić aby rzeczona metoda była dostępna (co nie zawsze jest wskazane), aby wywoływać ją z właściwymi parametrami – które też trzeba jakoś przekazać – i tak dalej… Krótko mówiąc na naszej drodze do ładnie zorganizowanego kodu naraz pojawia się sporo przeszkód.

Czy nie dałoby się po prostu jakoś przekazać tego “kawałka kodu”, tych kilku czy kilkunastu instrukcji opakowanych w coś, co można podać w inne miejsce programu?… Okazuje się, że jak najbardziej, a rozwiązaniem na problem refaktorowanych klas wewnętrznych jest… więcej klas wewnętrznych ;-) Nic nie stoi bowiem na przeszkodzie, aby rzeczony fragment procedury zdarzeniowej zapakować w metodę klasy implementującej interfejs Runnable. Tak, dokładnie ten interfejs który zazwyczaj kojarzy się z wątkami i klasą Thread. W rzeczywistości reprezentuje on “cokolwiek co da się uruchomić”, więc jak ulał pasuje w charakterze rozwiązania problemu.
Aplikując je do powyższego przykładu, możemy wydzielić powyższy listener (potencjalnie wraz z kilkunastoma podobnymi) i kazać mu jedynie wywoływać metodę run jakiegoś obiektu Runnable. W niej zaś umieszczamy nasz pierwotny kod i przekazujemy do nowo wydzielonej klasy:

  1. Buttons.setExitAction(new Runnable() {
  2.     @Override
  3.     public void run() { finish(); }
  4. }

Znawcy tematu powiedzieliby, że w ten sposób utworzyliśmy domknięcie (closure), bo w inne miejsce programu przekazaliśmy fragment kodu wraz z jego kontekstem; w tym przypadku jest to chociażby referencja this na rzecz której wywoływany jest finish. Fani programowania funkcyjnego stwierdzą z kolei, że ta technika jest kiepską imitacją wyrażeń lambda i najprawdopodobniej też będą mieli rację.
Nie zmienia to jednak faktu, że jeśli programujemy w starej (nie)dobrej Javie, to technika ta może być po prostu użyteczna – niezależnie od tego, jaki paradygmat za nią stoi. Dlatego też chciałem dzisiaj się nią podzielić.

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


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