Posts tagged ‘C/C++’

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

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

Pętla z wyróżnionym startem

2010-07-07 13:57

Jednym z powodów, dla których nie lubię diagramów blokowych, jest ich prymitywna notacja przedstawiania instrukcji sterujących. Jedyne, czym się tam dysponuje, to if i skok. Jak przy pomocy tylko tego można w klarowny sposób przedstawić jakikolwiek nietrywialny algorytm? To trochę tak, jakby w programowaniu używać tylko pętli nieskończonych i instrukcji break.
Można to robić, oczywiście, ale konsekwencje nie są zbyt ciekawe. Jeśli kryterium opuszczenia pętli jest tak skomplikowane, że trzeba je rozbić na kilka konstrukcji ifbreak i żadna z nich “nie zasługuje” na wyciągnięcie do warunku w samym while/for, to coś tu brzydko pachnie. Nie chciałbym być w skórze tego, kto będzie musiał później takie dzieło debugować.

W bardziej rozsądnych przypadkach da się uniknąć pętli nieskończonych, nawet jeśli od razu nie widać, jak można by to zrobić. I tak odkryłem na przykład, jak można to ładnie zrobić w sytuacji podobnej do poniższej:

  1. T foo;
  2. for (;;)
  3. {
  4.     foo = SomeFunction(sth);
  5.     if (!foo.IsOK()) break;
  6.  
  7.    // (Reszta pętli, zmieniająca sth na podstawie foo)
  8. }

Nazywam to pętlą z wyróżnionym startem, bo typowa jej postać, która nie zawiera (pozornie) nieskończonego kręcenia się w kółko, wygląda tak:

  1. for (T foo = SomeFunction(sth); foo.IsOK(); foo = SomeFunction(sth))
  2.     { /* Reszta pętli, jw. */}

Cała zabawa polega na tym, że pierwsze wywołanie SomeFunction może dać niepoprawną wartość w foo. (Może to być jakieś wyszukiwanie w pojemniku i element odpowiadający kluczowy sth nie został w ogóle znaleziony). Sama treść pętli nie może być wtedy wykonana, bo zdarzy się zapewne jakieś nieszczęście. Dlatego trzeba wyodrębnić to pierwsze wywołanie, i oczywiście zadbać także o kolejne. A to daje, jak widać, dublowanie kodu. Chciałoby się to zrobić lepiej.

I można, na szczęście. Możemy za to podziękować feature‘owi C++, który często bywa krytykowany jako ułatwiający popełnianie błędów. Bowiem to dzięki temu, że instrukcja przypisania zwraca wartość przypisywaną, możemy to wszystko zapisać tak:

  1. for (T foo; (foo = SomeFunction(sth)).IsOK(); /* nic */)
  2.     { /* Reszta pętli */ }

Zdaję sobie sprawę, że dla wielu fakt ten jest równie oczywisty jak pisanie return a == b; zamiast:

  1. if (a == b) return true; else return false;

ale dla niektórych taka postać pętli for może być zupełnie zaskakująca. Pamiętajmy, że kiedyś (prawie) każdy pisał też i takie ify jak powyżej ;-)

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

Split

2010-07-02 17:44

Tytuł dzisiejszej notki nie ma nic wspólnego z miejscowością wypoczynkową na południu Chorwacji, chociaż pewnie obecne temperatury nasuwają takie skojarzenia :) Zamiast tego chodzi o split łańcucha znaków, czyli bardzo często potrzebną w praktyce operację na stringach.
Danymi dla niej są najczęściej dwa napisy, zaś wynikiem jest tablica podciągów pierwszego z nich, powstała poprzez podzielenie go względem wystąpień drugiego (tzw. separatora). Ponieważ jak zwykle przykład będzie mówił najwięcej, niniejszym podaję nawet kilka:

  1. Split("Ala ma kota", " ") == { "Ala", "ma", "kota" };
  2. Split("1, 2, 3, 4", ",") == { "1", " 2", " 3", "4" };
  3. Split("<point x='23' y='14' z='-3' />", " ")
  4.     == { "<point", "x='23'", "y='14'", "z='-3'", "/>" }

Zwłaszcza ostatni pokazuje, że split jest rzeczywiście użyteczną funkcją, mogącą ułatwiać parsowanie formatów tekstowych (zwłaszcza, jeśli daje się ją zastosować wielokrotnie). Warto więc mieć takową w swoim języku/bibliotece. Jak więc przedstawia się jej dostępność na różnych platformach?

Tradycyjnie w .NET i Javie jest dobrze, a nawet lepiej. W obu przypadkach funkcja (a właściwie metoda) Split/split klasy String dodaje nawet trochę więcej możliwości niż to opisałem wyżej. I tak w .NET można podać więcej niż jeden oddzielacz, natomiast w Javie domyślnie może być nim również wyrażenie regularne.
Niektóre języki skryptowe i skryptopodobne też mają się w tym względnie całkiem dobrze. W Pythonie jest metoda split w klasie napisu, natomiast PHP ma funkcję explode, która mimo innej nazwy działa bardzo podobnie.

Ale nie wszędzie funkcja typu split jest od razu dostępna; niekiedy trzeba ją sobie samemu napisać. Przykładem języka, gdzie może być to koniecznie, jest Lua oraz – jakżeby inaczej – C++ :) Ze względu na użyteczność splita często znajdowałem się w sytuacji, gdzie konieczne/wygodne było jego napisanie. Po kilku(nastu?) takich przypadkach doszedłem wreszcie do czegoś podobnego do poniższego kodu:
typedef std::vector StringArray;
StringArray Split(const std::string& text, const std::string& delim)
{
StringArray res;
if (delim.empty()) { res.push_back(text); return res; }

std::string::size_type i = 0, j;
while (i < text.length() && (j = text.find(delim, i)) != std::string::npos) { res.push_back (text.substr(i, j - i)); i = j + delim.length(); } res.push_back (text.substr(i)); return res; }[/cpp] Na koniec zwrócę jeszcze uwagę na to, że czasami trzeba ostrożnie postępować z rezultatem splitu. Zdecydowana większość wersji tej operacji dopuszcza, by w wynikowej tablicy występowały puste ciągi. Odpowiadają one kilku kolejnym wystąpieniom separatora lub jego obecnością na początku bądź końcu ciągu. Jeśli nie są one nam potrzebne (a rzadko są), to należy je zignorować lub usunąć.

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

Dokładny czas na wielu platformach

2010-06-26 23:54

Gry i inne podobne aplikacje wymagają precyzyjnego pomiaru czasu, aby realizować obliczenia związane z fizyką, animacją, itp. Jak niemal wszystko, API potrzebne do tego celu jest różne w zależności od platformy, czyli (głównie) systemu operacyjnego. Dzisiaj chciałbym pokazać, jak wygląda to na dwóch najpopularniejszych systemach: Windows i POSIX (a więc między innymi na wszelkiego typu Linuksach).

Interfejs programistyczny systemu spod znaku okienek udostępnia dwie funkcje od dokładnego mierzenia czasu. Są to QueryPerformanceFrequency i QueryPerformanceCounter. Tę pierwszą wywołuje się tylko raz, a jej wynikiem jest częstotliwość wewnętrznego systemowego zegara, który służy do precyzyjnego pomiaru upływającego czasu. Wyrażana jest ona w liczbie “tyknięć” na sekundę i na dzisiejszym sprzęcie może być bardzo duża, bo liczona w (kilku(nastu/dziesięciu)) milionach.
Druga funkcja jest używana nieporównywalnie częściej, gdyż to ona zwraca aktualną wartość zegara, czyli liczbę jego “tyknięć”. Stąd wynika, że obliczenie tej wartości w sekundach wymaga podzielenia rezultatu QPC przez uzyskaną wcześniej częstotliwość:

  1. LARGE_INTEGER freq, counter;
  2. QueryPerformanceFrequency (&freq);
  3. // ...
  4. QueryPerformanceCounter (&counter);
  5. double secs = counter.QuadPart / (double)freq.QuadPart;

Używana tu unia LARGE_INTERGER to nic innego, jak zwykła liczba 64-bitowa.

W systemach POSIX-owych rzecz jest odrobinę prostsza, jako że tutaj dokładność zegara jest ściśle ustalona. Funkcja gettimeofday (z nagłówka sys/time.h) zwraca rezultat z precyzją mikrosekundową w postaci struktury timeval:

  1. struct timeval tv;
  2. gettimeofday (&tv, 0);
  3. double sec = tv.tv_sec + tv.tv_usec / 1000000.0;

Część odpowiadającą niepełnym sekundom (pole tv_usec) trzeba więc podzielić przez milion.

Chcąc mieć bardziej uniwersalne rozwiązanie, możemy napisać klasę opakowującą zegar z implementacją kontrolowaną docelową platformą, na którą kompilujemy:

  1. class Clock
  2. {
  3.     #ifdef _WINDOWS
  4.         LARGE_INTEGER freq;
  5.         public: Clock() { QueryPerformanceFrequence (&freq); }
  6.     #endif
  7.  
  8.     double GetTicks() const
  9.     {
  10.         #ifdef _WINDOWS
  11.             LARGE_INTEGER counter;
  12.             QueryPerformanceCounter (&counter);
  13.             return counter.QuadPart / (double)freq.QuadPart;
  14.         #else
  15.             struct timeval tv; gettimeofday (&tv, 0);
  16.             return tv.tv_sec + tv.tv_usec / 1000000.0;
  17.         #endif
  18.     }
  19. };

Można by na koniec zapytać jeszcze, co tak naprawdę znaczy zwracana wartość zegara. Kiedy wynosi ona zero?… Otóż wbrew pozorom odpowiedź na to pytanie nie jest istotna, bo w praktyce interesuje nas tylko interwał czasowy, tj. różnica między dwoma wskazaniami timera. To na jej podstawie liczymy zmianę w prędkościach obiektów, klatkach animacji czy w końcu niezbędnie konieczną do wyświetlenia wartość FPS :)

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

Szablony klas i funkcje zaprzyjaźnione

2010-06-04 21:18

Chcę dzisiaj napisać o pewnego rodzaju “ciekawostce”, związanej z dwoma pojęciami z tytułu notki, na którą natknąłem się jakiś czas temu. Po zredukowaniu nadmiaru szczegółów można przyjąć, że rzecz dotyczy sytuacji, w której mamy szablon klasy oraz zadeklarowaną wewnątrz niego funkcję zaprzyjaźnioną – na przykład przeciążony operator strumieniowy <<:

  1. #include <iostream>
  2.  
  3. template <typename T> class Foo
  4. {
  5.     private: T x;
  6.     public:
  7.         explicit Foo(T _x) : x(_x) { }
  8.         friend std::ostream& operator << (std::ostream& out, const Foo<T>& foo);
  9. };

Funkcja jest zadeklarowana, lecz nie jest od razu zaimplementowana wewnątrz bloku class. Zamiast tego umieszczamy jej kod osobno:

  1. template <typename T> std::ostream& operator << (std::ostream& out, const Foo<T>& foo)
  2.     { return out << foo.x; }&#91;/cpp]
  3. co jest może trochę osobliwe, ale wydaje się poprawne. No właśnie; wydaje się. Próba użycia tak zdefiniowana operatora:
  4. &#91;cpp]Foo<int> foo(42);
  5. std::cout << foo << std::endl; // bum[/cpp]
  6. nie przeszkadza wprawdzie kompilatorowi, jednak linker ma poważne zastrzeżenia. Okazuje się, że funkcja <code>operator &lt;&lt;</code> w wymaganej postaci nie jest zdefiniowana - czyli mamy zwyczajny <em>unresolved external</em>, aczkolwiek o niecodziennych przyczynach.
  7.  
  8. Przyznać muszę teraz, że nie jestem do końca pewien co do ich natury, jako że konsultacja z zaufanymi źródłami (w postaci książki <a href="http://helion.pl/ksiazki/c_szablony_vademecum_profesjonalisty_david_vandevoorde_nicolai_m_josuttis,cpszav.htm"><em>C++. Szablony</em></a> panów Vandevoorde'a i Josuttisa) nie dała jednoznacznej odpowiedzi, co tutaj tak naprawdę się dzieje. Przypuszczam, że ma tu miejsce pewien dziwnej interakcji między konkretyzacją szablonu klasy a deklaracją <code>friend</code>, która przy okazji jest też deklaracją funkcji <code>operator &lt;&lt;</code>. Mimo że nie stanowi ona części szablonu, owej konkretyzacji <strong>podlega</strong>, czego skutkiem jest stworzenie <strong>zwykłej</strong> (nieszablonowej) deklaracji:
  9. [cpp]std::ostream& operator << (std::ostream& out, const Foo<int>& foo);

Nie ma więc ona nic wspólnego z szablonem funkcji operator <<, który jest zdefiniowany później! W rzeczywistości wygląda zresztą tak, że ów szablon jest całkowicie pominięty przy kompilacji jako niewykorzystywany; to zapewne z powodu reguł przeciążania funkcji w C++, nakazujących najwyraźniej wybranie raczej funkcji nieszablonowej (o powyższej deklaracji) zamiast szablonu funkcji. A że przypadkiem funkcja ta nie ma implementacji… Cóż, kompilator nie ma obowiązku się o to martwić :)

Tyle moja teoria. Niezależnie od tego, czy jest ona prawdziwa czy nie, dobrze byłoby wiedzieć, jak z problemu wybrnąć. Naturalnym wyjściem jest przenieść kod funkcji tam, gdzie jego miejsce – czyli z deklaracji funkcji w klasie (opatrzonej słówkiem friend) uczynić też jej definicję. Faktycznie, to działa; najwyraźniej powstaje wtedy nieszablonowa funkcja o nagłówku danym wyżej, razem ze swoją implementacją – czyli wszystko jest w porządku.
Drugie rozwiązanie to opatrzenie deklaracji friend klauzulą template:

  1. template <typename T>
  2.     friend std::ostream& operator << (std::ostream& out, const Foo<T>& foo);

W tej wersji – jak sądzę – następuje zaprzyjaźnienie każdej specjalizacji klasy Foo z odpowiadającą jej specjalizacją metody operator <<. Oba szablony podlegają niezależnym konkretyzacjom, ale linker potrafi prawidłowo rozwiązać relację między nimi.

Uff, trochę to skomplikowane. Jak widać, z zaprzyjaźnianiem bywają problemy – i to nie tylko dlatego, iż “In C++ friends touch each other’s private parts.” ;) Dziwne efekty związane z szablonami i konkretyzacją potrafią bowiem skonfudować nawet doświadczonych programistów.

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

Dwukierunkowe funkcje i obiekty proxy

2010-06-01 16:07

Jedną z pierwszych rzeczy poznawanych w trakcie nauki programowania jest sposób działania funkcji. Mam tu na myśli zupełnie elementarny fakt, iż funkcje przyjmują zero lub więcej argumentów na wejściu i produkują co najwyżej jeden rezultat na wyjściu. Niezachwiana pewność w tę własność funkcji może być potem mocno nadwątlona, jeśli poznamy języki o bardziej egzotycznym sposobie działania, jak na przykład Prolog; tam wszystkie parametry funkcji mogą przekazywać dane w obu kierunkach, dzięki czemu np. za dzielenie i łączenie ciągów lub list odpowiada jedna i ta sam funkcja.
Nie trzeba jednak uciekać tak daleko od starego dobrego programowania imperatywnego, żeby zaobserwować odstępstwa od reguły. Parametry mogą przecież służyć do zwracania wartości – dzieje się to przy pomocy słów kluczowych ref/out w C# lub zwykłych wskaźników/referencji w C++. Często zdarza się wtedy, że “normalny” rezultat zwracany przez funkcję służy jedynie przekazaniu informacji o ewentualnym błędzie.

Rzadsza sytuacja polega na tym, że wynik funkcji staje się jej argumentem wejściowym. Technicznie nie jest nawet możliwe, ale można tak traktować sytuacje, gdy rezultatem jest l-wartość (l-value), tj. obiekt, do którego można przypisywać:

  1. vector<int> v(10);
  2. v.at(5) = 25;

Typowo jest to referencja (tutaj int&), a powyższa konstrukcja – poprzez swojej podobieństwo do indeksowania zwykłej tablicy – nie należy do wielce zaskakujących. Co jednak można powiedzieć o tej:

  1. Dim S as String = "Ala ma kota"
  2. Mid(S, 4, 2) = "nie ma" ' Ala nie ma kota

poza widocznym od razu faktem, że pochodzi ona z języka, którego rozwlekłość składni przyprawia o niestrawność? :) Mianowicie tutaj nie ma już oczywistych przesłanek co do tego, czym jest lewa strona. Widać bowiem, że możemy jej przypisać dłuższy podciąg niż oryginalny i zostanie on mimo wszystko poprawnie zastąpiony – nie jest to więc żaden prosty “wyrób wskaźnikopodobny”. Może więc to po prostu feature akurat tego języka, którego nie da się zreplikować?…

Odpowiedź jest – jak można się domyślać, skoro o tym piszę – oczywiście negatywna :) Ażeby podobny efekt osiągnąć w C++, konieczne jest jednak zastosowanie techniki znanej jako obiekt pośredniczącyproxy. Powinien on zachowywać się jak zwykły rezultat funkcji, ale w razie potrzeby dawać również możliwość przypisywania do siebie. Naturalnie efekt takiego działania jest specyficzny dla konkretnej funkcji, która swoją drogą może być często zredukowana do samego tworzenia obiektu proxy:

  1. inline Mid_Proxy Mid(std::string& s, size_t off, size_t len)
  2.     { return Mid_Proxy(s, off, len); }

Minimum, jakie rzeczony obiekt musi zapewniać, to operator przypisania oraz jakiś operator rzutowania, który pozwoli na “wyciągnięcie” rezultatu funkcji, gdy jest ona użyta w zwykły sposób:

  1. class Mid_Proxy
  2. {
  3.     private:
  4.         std::string& s;
  5.         size_t off, len;
  6.     public:
  7.         Mid_Proxy(std::string& _s, size_t _off, size_t _len)
  8.             : s(_s), off(_off), len(_len) { }
  9.  
  10.         void operator = (const std::string& str)
  11.             { s.replace (off, len, str); }
  12.         operator std::string () const
  13.             { return s.substr(off, len); }
  14. };

Widzimy tutaj, że przy takim proxy nasza funkcja Mid użyta w zwykły sposób zachowuje się jak metoda substr. Gdy jednak umieścimy jej wywołanie po lewej stronie przypisania, zadziała metoda replace, służąca do zastępowania podciągu innym. W sumie więc poniższy kod:

  1. std::string s("Ala ma kota");
  2. Mid(s, 4, 2) = "nie ma";

będzie działał analogicznie do prezentowanego wyżej fragmentu w języku Visual Basic.

Opisana tu sztuczka nie jest oczywiście doskonała. Do pełni możliwości potrzebna jest jeszcze wersja read-only funkcji Mid, przyjmująca stałą referencję do stringa i wywołująca substr bezpośrednio, z pominięciem obiektu proxy. To jednak da się łatwo zauważyć.
Mniej widoczny jest natomiast fakt, że obiekt proxy, dodając kolejną warstwę niejawnych konwersji (tutaj: z siebie na string) może spowodować kłopoty tam, gdzie jedna niestandardowa konwersja jest już wykorzystywana. Dobry przykład to interakcja ze strumieniem:
std::cout << Mid(s, 0, 3) << std::endl;[/cpp] która nie powiedzie, bo operator strumienowy << nie posiada wersji dla lewego prawego argumentu będącego std::stringiem, a jedynie dla const char* (co swoją drogą jest dość dziwne). Rozwiązaniem jest napisanie takowego dla samego obiektu proxy.

 


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