Archive for Programming

Maksimum, minimum

2010-09-30 18:52

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.

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

Udekorowane funkcje

2010-09-22 16:46

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:

  1. import logging
  2.  
  3. def vif(): # Very Important Function :)
  4.     logging.debug("Called function vif()")
  5.     # ...

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 tryfinally. 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:

  1. @trace
  2. def vif():
  3.     # ...

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:

  1. import logging
  2.  
  3. def trace(func):
  4.     def _func(*args, **kwargs):
  5.         logging.debug("Calling function %s()", func.__name__)
  6.         return func(*args, **kwargs)
  7.  
  8.     return _func

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:

  1. # Ta funkcja wymaga połączenia z serwerem!
  2. def do_something():
  3.     # ...

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.

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

Zabezpieczenie przed NULL-em

2010-09-18 22:36

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:

  1. if (!p) return false;
  1. if (arg == null) throw new ArgumentNullException("arg");

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

  1. if (p && p->key == k) return p;

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

  1. string str = s != null ? s : "N/A"; // C++/C#/Java
  1. s = s if s != None else "N/A" # Python

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

  1. string str = s ?? "N/A";

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:

  1. int? x = null; // liczba typu int lub null
  2. int y = x ?? -1; // ustaw y = -1; jeśli x == null

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

Tags: , , ,
Author: Xion, posted under Programming » Comments Off on Zabezpieczenie przed NULL-em

Zamiast klawisza F7

2010-09-11 12:19

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:

  1. make
  2. make install

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 :)

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

Androidowa biblioteka do screenów

2010-09-08 10:46

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 :)

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

Python, wcięcia i bardzo wredny błąd

2010-09-04 17:13

Niektórzy programiści, rozmawiając z innymi, znajdują przyjemność we wskazywaniu na specyficzne cechy różnych języków programowania, które im nie odpowiadają. Nie uważam tego za specjalnie produktywne i samemu staram się tego unikać. W końcu co za różnica, że w Javie czy C++ mamy nawiasy klamrowe, w Pascalu begin i end, a w Pythonie bloki wyróżniane wcięciami? Dla sprawnego programisty nie powinno to mieć żadnego znaczenia.
I faktycznie jest – dopóki nie okaże się, że pozornie nieistotna cecha języka prowadzi do błędów. Nieprzyjemnych, wrednych i trudnych do wykrycia błędów. Tak, wtedy dyskutowanie o podobnych składniowych błahostkach może być choć częściowo usprawiedliwione…

A skoro sam ten temat podjąłem, to wymaga mi przedstawić moje usprawiedliwienie. Nie jest ono długie. Wygląda bowiem tak:

  1. def escape_chars(text):
  2.     result = []
  3.     for c in text:
  4.         if ord(c) > 255:
  5.             result.append ("&#%s;" % ord(c))
  6.     else:
  7.         result.append (c)
  8.     return ''.join(result)

Ta prosta pythonowa funkcja ma za zadanie zamienić w podanym tekście znaki spoza zakresu ANSI na ich XML-owe odpowiedniki w postaci encji numerycznych (np. &#456;). Niezbyt skomplikowane, prawda? A jednak całkiem długo zajęło mi dojście do tego, czemu dla tekstu z samymi znakami ANSI wynikiem jest… łańcuch pusty.

Jest oczywiście bardzo prawdopodobne, że ktoś patrząc teraz na powyższy kod znajdzie przyczynę w mniej niż dziesięć sekund – zwłaszcza, że niemal bezpośrednio zasugerowałem ją na samym początku. To naturalnie nie świadczy o niczym, bo napady specyficznego rodzaju ślepoty na rzeczy oczywiste są nieodłączną częścią zajęcia zwanego programowaniem :) Z tym nie ma sensu polemizować.
Ale jak najbardziej można dyskutować o tym, dlaczego “wrodzona” cecha składni języka uważanego za nieskomplikowany, efektywny i nowoczesny (cokolwiek to znaczy) może być bezpośrednią przyczyną powstawania błędów, o którym użytkownikom C, Javy czy Pascala nawet się nie śniło! Nie widzę innego wytłumaczenia oprócz krótkowzroczności projektantów języka, którzy nie potrafili uświadomić sobie, że jego feature‘y mogą wchodzić ze sobą nie tylko w pożyteczne, ale czasem i niepożądane interakcje.

Dla jasności wytłumaczę jeszcze dokładniej, w czym rzecz. Mianowicie w Pythonie koniec bloku kodu rozpoznawany jest nie obecnością terminatora w rodzaju } czy end, lecz zmianą poziomu wcięcia następnej linijki – czyli czymś, co w innych językach pełni rolę wyłącznie estetyczną. Wiersze mające tę samą liczbę początkowych spacji leżą więc na tym samym poziomie zagłębienia.
Stąd zaś wynika fakt, iż w powyższej funkcji fraza else nie jest wcale dołączona do instrukcji if, lecz do… pętli for. Prawidłowe zagnieżdżenie wygląda bowiem tak:

  1. def escape_chars(text):
  2.     result = []
  3.     for c in text:
  4.         if ord(c) > 255:
  5.             result.append ("&#%s;" % ord(c))
  6.         else:
  7.             result.append (c)
  8.     return ''.join(result)

Ale chwilka – jak pętla for może mieć else‘a?… Ano to już jest rzecz specyficznie pythonowska (a biorąc pod uwagę okoliczności, wręcz monty-pythonowska), którą zresztą kiedyś zdarzyło mi się opisać. Wówczas to określiłem ją tylko jako zawracanie głowy. Dzisiaj porównałbym ją raczej z możliwością wpisywania stałych ósemkowych w kodzie C. Oba feature‘y używane są świadomie średnio raz na trzy lata, przez resztę czasu potencjalne powodując jedynie błędy.

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

Odpalanie klasy

2010-08-31 12:09

Niskopoziomowe, wewnętrzne klasy logiki mają tę wadę (jeśli można to tak nazwać…), iż są właśnie niskopoziomowe i wewnętrzne – a przez to trudne do testowania w powiązaniu z całą aplikacją. Między nimi a interfejsem może znajdować się wiele warstw, które utrudniają debugowanie.
To sprawia, że przydatne stają się testy jednostkowe (unit tests). Do ich tworzenia i uruchamiania potrzeba jednak odpowiednich frameworków. Na szczęście te są już dostępne dla niemal każdego sensownego języka programowania i nierzadko są wręcz częścią jego lub jego środowiska.
Nie zawsze jednak tak było. Alternatywą dla ręcznego tworzenia specjalnych aplikacji przeznaczonych wyłącznie do testowania klas były (i właściwie nadal są) interesujące mechanizmy “uruchamiania klas” jako takich, które oferują niektóre języki programowania.

Dotyczy to przede wszystkim – jeśli nie wyłącznie – tych spośród nich, w których koncepcja programu czy aplikacji nie jest wyraźnie zakreślona. Coś jakiego jak entry point (“punkt wejścia”), od którego zaczyna się wykonywanie kodu, musi jednak istnieć i trzeba mieć jakiś sposób na jego określenie. Jeżeli zamiast aplikacji mamy tylko mniej lub bardziej luźny zbiór klas, to siłą rzeczy musi się on znajdować w którejś z nich.
A jeśli znajduje się w jednej, to czemu nie dodać go też do innych – także tych, które z założenia nie mają pojęcia o interakcji z użytkownikiem? Tworzymy w ten sposób pewnego rodzaju back-end, a owe dodatkowe punkty wejścia mogą posłużyć do testów. Oto prosty przykład w języku Java:
public class Sumator
{
private int sum = 0;
public void add(int x) { sum += x; }
public int getSum() { return sum; }

// testowy punkt wejścia
public static void main(String[] args) {
int n = args.length > 1 ? Integer.parseInt(args[1]) : 100;

Sumator s = new Sumator();
for (int i = 1; i <= n; ++i) s.add(i); System.out.println ("Spodziewana suma: " + (n * (n + 1) / 2)); System.out.println ("Otrzymana suma: " + s.getSum()); } }[/java] Statyczna metoda main to w Javie sposób na określenie punktu wejścia. Typowym miejscem dla niego jest główna klasa aplikacji, względnie całkiem osobna klasa przeznaczona do zarządzania samym uruchamianiem programu. Tutaj umieszczamy metodę main w klasie logiki (bardzo zaawansowanej zresztą ;-]), przez co możemy “odpalić” samą tę klasę i wykonać jakiś kod testujący jej funkcjonalność.

Z popularnych języków mających taki feature można jeszcze wspomnieć Pythona. W nim obiektowość nie jest obowiązkowa, więc to skrypt (plik .py) jest podstawową jednostką kodu, którą można uruchamiać:

  1. import sys
  2.  
  3. class Sumator:
  4.     def __init__(self): self.sum = 0
  5.     def add(self, x): self.sum += x
  6.  
  7. if __name__ == "__main__":
  8.     n = int(sys.argv[1]) if len(sys.argv) > 1 else 100
  9.     s = Sumator()
  10.     for i in range(1, n+1): s.add(i)
  11.     print "Spodziewana suma: ", (n * (n + 1) / 2)
  12.     print "Otrzymana suma: ", s.sum

Daje się w nim też umieścić “swobodny” kod, co na pierwszy rzut oka wydaje się dobrym miejscem na instrukcje testowe. Trzeba tylko otoczyć je pokazanym wyżej ifem, aby były one uruchamiane wyłącznie przy wywoływaniu skryptu z wiersza poleceń, nie zaś przy imporcie zawartego w nim kodu (instrukcją import).

Tags: , , , ,
Author: Xion, posted under Programming » Comments Off on Odpalanie klasy
 


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