Posts from 2011

Mniej CSS-a

2011-07-11 19:28

Ktokolwiek, kto pisał dłuższy lub bardziej skomplikowany arkusz stylów CSS, wie jakim bólem siedzenia potrafi to być. Nie chodzi tu nawet o same style, których interakcje między sobą oraz z zawierającymi je selektorami mogą czasem być cokolwiek zagadkowe (tak, marginy i paddingi – o was mówię). Rzecz w tym, że sam język CSS jest po prostu biedny – nie tyle w zakresie możliwości (w końcu jest zupełny w sensie Turinga), co wygody użytkowania. Brakuje mu chociażby kilku kluczowych konstrukcji, jakich można by się spodziewać. Dobrym przykładem są stałe (zmienne) i możliwość wykonywania na nich operacji arytmetycznych – choćby w celu policzenia zależnych od siebie marginesów.

Z tą bolączką można sobie oczywiście radzić we własnym zakresie, podłączając na przykład arkusze CSS pod system szablonów normalnie używany do generowania stron HTML na poziomie serwera. Nie wydaje się to jednak najlepszym możliwym sposobem na zużywanie jego zasobów. Istnieją też na pewno bardziej interesujące rzeczy, które mógłby zrobić programista w czasie, gdy będzie takie (z natury raczej specyficzne) rozwiązanie implementował.

I tutaj pojawia się bardzo ciekawy projekt o nazwie LESS, rozszerzający składnię CSS-a o wiele przydatnych elementów, jakich domyślnie w nim nie uświadczymy. Najfajniejsze jest przy tym to, że trik ten odbywa się po stronie klienta przy pomocy odpowiedniego skryptu JavaScript. Możemy więc korzystać z niego niezależnie od backendu naszego serwera czy nawet w ogóle bez serwera, tj. do stron bez dynamicznie generowanej treści. Integracja jest zaś bardzo prosta: sprowadza się do dodania jednego znacznika <script> (oczywiście) oraz lekkiej modyfikacji referencji do arkuszy stylów, czyli znaczników <link rel="stylesheet">.

Co dostajemy w zamian? Oprócz wspomnianych na początku zmiennych i operacji na nich, mamy też w LESS-ie “funkcje” (czy raczej makra) z parametrami. Pozwala to chociażby na łatwiejsze dostarczanie stylów specyficznych dla przeglądarek. Możliwe jest też np. importowanie kodu z innych arkuszy LESS, zagnieżdżanie selektorów oraz… wstawianie komentarzy w stylu C++ :)
Powyższe wyliczenie dodatków nie brzmi może bardzo imponująco, lecz nie jest to wcale dziwne. Tak naprawdę sam CSS już dawno powinien oferować tego rodzaju możliwości. Wiemy jednak, jak jest w rzeczywistości. Sądzę więc, że tym bardziej warto jest używać rozwiązania, które zamienia CSS w coś, czego można w końcu normalnie używać :)

Tags: ,
Author: Xion, posted under Internet » 10 comments

Prezentacja nt. Google App Engine

2011-07-06 20:18

W zeszły piątek wziąłem udział w kolejnym evencie organizowanym przez warszawski oddział polskiej Grupy Użytkowników Technologii (w skrócie GTUG). Nie było to ponadto uczestnictwo pasywne. Wspólnie z kolegą z pracy wygłosiłem tam bowiem półtoragodzinną prezentację na temat technologii Google App Engine, czyli platformy do tworzenia aplikacji sieciowych, działającej w oparciu o ideę cloud computing.
Nosiła ona jakże pogodny tytuł Rozchmurz się! i przedstawiała całą platformę właściwie od podstaw, ale jednocześnie w jak najszerszym przekroju. Dodatkowo nie obyło się oczywiście bez kilku odniesień do osobistych doświadczeń z jej użytkowania. Ogólnie wydaje mi się, że mimo wyraźnie wieczorowej pory udało nam się nie uśpić publiczności całkowicie ;-)

Zamieszczam poniżej slajdy z prezentacji. Na stronie GTUG można natomiast obejrzeć galerię zdjęć z całego wydarzenia. Na dniach powinien również pojawić się filmik.

File: Rozchmurz sie! -- Cloud computing z Google App Engine [PL]  Rozchmurz sie! -- Cloud computing z Google App Engine [PL] (805.8 KiB, 1,470 downloads)

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?…

 


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