Posts tagged ‘C/C++’

Badania terenowe nad budowaniem stringów

2009-07-18 13:04

Cokolwiek kodujemy, konieczność zbudowania dużego łańcucha znaków składającego się z kolejno dołączanych fragmentów pojawia się bardzo często. To może być zapytanie do bazy danych, misternie wyrzeźbiony adres URL, dynamicznie generowany i kompilowany później shader czy w końcu obszerny i szczegółowy komunikat o błędzie.
Wspólną cechą tych tekstów jest to, że budujemy je stopniowo, kawałek po kawałku. Na takie okazje niektóre języki (jak .NET-owe lub Java) posiadają specjalne klasy w rodzaju StringBuilder. Mają one być efektywniejsze niż bezpośrednie używanie typów string, głównie ze względu na nietworzenie wielu łańcuchów i niezaśmiecanie nimi pamięci, co odciąża garbage collector z dodatkowej pracy.

W C++ nie ma oczywiście odśmiecacza, który musiałby po nas sprzątać, i nie ma też narzędzi typu StringBuilder. Czy to oznacza więc, że możemy radośnie korzystać z samej klasy std::string do budowania dowolnie długich tekstów, bo żadnej efektywniejszej alternatywy nie ma?… To właśnie zdecydowałem się sprawdzić, przeprowadzając mały eksperyment z tworzeniem długich łańcuchów znaków kilkoma sposobami, aby potomni nie musieli rozwiązywać tego jakże uciążliwego dylematu ;]
Przechodząc do rzeczy, wpierw wysmażyłem taką oto funkcję która generuje tekst o podanej minimalnej długości:

  1. const string GenerateString(string::size_type minLen)
  2. {
  3.     string res;
  4.     string::size_type currLen = 0;
  5.  
  6.     while (currLen < minLen)
  7.     {
  8.         string::size_type next = rand() % (MAX_FRAG_LEN + 1);
  9.         res += STRINGS&#91;next];
  10.         currLen += next;
  11.     }
  12.  
  13.     return res;
  14. }&#91;/cpp]
  15. Użyta w niej tablica <code>STRINGS</code> zawierała przygotowane wcześniej "kawałki" w postaci losowych napisów, z których składany był wynikowy tekst. Każdy element <code>STRINGS[n]</code> był tu tekstem o długości <code>n</code> znaków (z zakresu 0 do 111).
  16. Powyższej funkcji użyłem następnie do wygenerowania stringów o długościach 222.222, 555.555, 1.111.111, 5.555.555 i 11.111.111 znaków, mierząc czas każdej z tych operacji i uśredniając go z 10 powtórzeń. Skąd takie długości tych tekstów?... No cóż, tylko co najmniej takie wartości dawały sensowne i wystarczają długie czasy, które dawało się zmierzyć i porównać z innymi :)
  17.  
  18. No właśnie - a jakież to inne sposoby na konstruowanie napisów można było jeszcze wymyślić? Otóż wymyśliłem jeszcze dwa, polegające na wykorzystaniu wektora znaków (<code>vector&lt;char&gt;</code>). Operacja konkatenacji została w nich zaimplementowana jako rozszerzenie wektora (metoda <code>resize</code>), a następnie przekopiowanie zawartości stringa w powstałe miejsce - czyli mniej więcej tak:
  19. [cpp]// res to vector<char>
  20. res.resize (currLen + next);
  21. memcpy (&res[currLen], STRINGS[next].data(), next * sizeof(char));

Wyróżnienie dwóch sposobów polegało natomiast na tym, że w jednym z nich dodatkowo wywoływałem na samym początku metodę reserve w celu uprzedniej rezerwacji pamięci w wektorze na 3 * minLen / 2 elementów.

Testy przeprowadziłem na standardowej implementacji klas string i vector dostępnej w Visual C++ 2005. Wyniki eksperymentu przedstawiają się następująco:

Można w nich przede wszystkim zauważyć, że zarządzanie pamięcią w klasie string jest domyślnie znacząco lepsze niż w vector. Najszybszą metodą konstruowania napisów okazuje się jednak użycie wektora z uprzednią rezerwacją pamięci, która okazuje się o ok. 20% szybsza niż zwykła konkatenacja stringów.

Czy to oznacza, że powinniśmy stworzyć sobie własną klasę StringBuilder, opierającą się na wektorze właśnie, i jej używać? Niekoniecznie. Jak widać, znaczące różnice pojawiają się dopiero przy tworzeniu napisów o wielkościach rzędu megabajta lub więcej. Konia z rzędem temu, kto tworzy tak duże zapytania lub shadery :) Do większości typowych zastosowań bezpośrednie użycie typu string wydaje się więc wystarczające.
No chyba że istnieją bardziej efektywne sposoby na budowanie stringów w C++, których nie udało mi się wymyślić – co jest swoją drogą całkiem prawdopodobne :)

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

Sortowanie dla zaawansowanych

2009-07-02 18:06

Gdy trzeba posortować jakąś kolekcję w sposób – nazwijmy to – standardowy, to zwykle nie ma z tym problemu. Chyba każdy język posiada coś na takie okazje: mamy funkcję qsort, std::sort (i std::list::sort), System.Array.Sort, java.util.Arrays.sort, i tak dalej. Zwykle wystarczy podać im tablicę lub kolekcję i już mamy ją posortowaną.
Istnieją jednak przynajmniej dwie sytuacje, gdzie taka standardowa procedura nie jest wystarczająca. Jest tak na przykład wtedy, gdy:

  • zwykły sposób porównywania obiektów nie jest tym, którego chcielibyśmy używać przy sortowaniu. Ów “zwykły sposób” jest wyznaczany najczęściej przez operatory relacyjne (<, >=, itp.), które nie muszą być zdefiniowane (np. jeśli sortujemy obiekty własnego typu złożonego) lub mogą być określone inaczej niż byśmy w danym przypadku sortowania chcieli.
  • życzymy sobie odwrotnego porządku sortowania, czyli np. malejącego zamiast domyślnego rosnącego

W powyższych przypadkach rozwiązanie sprowadza się zwykle do zdefiniowania własnego kryterium porównawczego obiektów, które sortujemy. Spotyka się tu najczęściej dwie formy takiego kryterium:

  • W C++ możemy zdefiniować predykat binarny (funkcję przyjmującą dwa argumenty i zwracającą wartość binarny), który określa dla obiektów tzw. ścisłe uporządkowanie słabe (strict weak ordering). Mówiąc w skrócie, funkcja ta powinna mieć identyczne właściwości jak zwykły operator mniejszości <, czyli zwracać true, jeśli pierwszy obiekt jest “mniejszy” niż drugi. Jak nietrudno zauważyć, taka informacja jest wystarczająca do jednoznacznego uporządkowania dwóch obiektów. W szczególności a == b zachodzi wtedy i tylko wtedy, gdy !(a < b) && !(b < a), zatem taki predykat może też służyć do sprawdzania, czy dwa obiekty są sobie równe.
    Domyślnym predykatem sortowania w C++ jest std::less, który działa identycznie jak operator <. std::greater pozwala natomiast na odwrócenie porządku sortowania.
  • Wynik Relacja
    < 0 x < y
    == 0 x == y
    > 0 x > y

    W C, C# i w Javie korzysta się z kolei z funkcji porządkujących, które przyjmują dwa obiekty i zwracają w wyniku liczbę całkowitą. Liczba ta określa jednoznacznie uporządkowanie tych dwóch obiektów: czy jeden jest mniejszy niż drugi, równy mu czy większy od niego - tak, jak to pokazano w tabelce obok.
    Interesującą cechą takiego sposobu porządkowania jest to, że tak naprawdę używanie jakichkolwiek porównań (<=, > itp.) często nie jest w nim potrzebne. Zazwyczaj bowiem ową funkcję porównującą można zaimplementować następująco:

    1. int compare(x, y) { return val(x) - val(y); }

    gdzie val(x) oznacza tutaj pewną wartość liczbową przyporządkowaną obiektowi x, określającą jego miejsce w danym porządku sortowania. Wartość ta powinna być tak dobrana, aby posortowanie wszystkich takich liczb rosnąco dało nam w wyniku pożądaną kolejność uporządkowania naszych obiektów. Jeśli więc, przykładowo, chcemy posortować ciągi znaków w C# tak, by najdłuższe znalazły się na początku (czyli malejąco względem długości), to val(x) oznaczać tu będzie -x.Length().

Uff, jak widać sortowanie czasami nie jest wcale taką prostą sprawą :) Cieszmy się jednak, że nawet w bardziej skomplikowanych sytuacjach do napisania pozostają nam jedynie proste predykaty porównujące, nie zaś... całe algorytmy ;]

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

Funkcje jako dane wejściowe

2009-05-29 15:56

Sporo algorytmów jako swoje parametry przyjmuje różnego typu funkcje, które potem są wykorzystywane w trakcie ich działania. Prostym przykładem są tu wszelkiego rodzaju sortowania czy wyszukiwania, umożliwiające często podanie własnego predykatu (funkcji zwracającej wartość logiczną). W bardziej skomplikowanej wersji może chodzić chociażby o algorytm genetyczny lub przeszukujący drzewo gry, który wykorzystuje do działania jakąś funkcję oceniającą (np. osobników w populacji).

Na takie okazje różne języki programowania oferują różne narzędzia, lecz w większości przypadków sprowadzają się one do jednego z poniższych:

  • Wskaźniki lub delegaty. Przekazywanie funkcji przez wskaźnik jest proste i naturalne, ale ma pewne ograniczenia. W C(++) na przykład nie da się zwykłym wskaźnikiem pokazać na metodę konkretnego obiektu; docelowo może to być tylko funkcja globalna lub statyczna. Ten problem nie występuje zwykle w przypadku delegatów, którymi często można pokazać właściwie na wszystko – również na anonimową funkcję zdefiniowaną ad hoc:
    1. // sortowanie listy w oparciu o własny predykat (C# 2.0 wzwyż)
    2. objects.Sort (delegate (object a, object b)
    3.     { return a.ToString().Length - b.ToString().Length; });

    Niektóre języki nie mają jednak ani wskaźników, ani delegatów – w nich zwykle stosuje się sposób następny.

  • Interfejsy i metody wirtualne. Ta technika polega na zdefiniowaniu interfejsu (lub klasy abstrakcyjnej) z metodą wirtualną, którą docelowo będzie wywoływać algorytm. Korzystający z niego programista implementuje po prostu wskazany interfejs (lub definiuje klasę pochodną) i nadpisuje wspomnianą metodę własną wersją. Ten sposób jest szczególnie popularny w Javie, gdzie wspomagają go inne mechanizmy językowe – jak choćby niestatyczność klas wewnętrznych lub możliwość ich definiowania inline – np. w wywołaniu funkcji.
    Zauważmy też, że implementacja naszej ‘funkcji’ w postaci klasy pozwala też na dodatkowe możliwości, jak na przykład posiadanie przez nią stanu (co aczkolwiek w wielu przypadkach, np. predykatów sortowania, jest wysoce niezalecane).
  • Funktory. To rozwiązanie jest specyficzne dla C++ i opiera się na dwóch występujących w tym języku feature‘ach: szablonach i przeciążaniu operatorów. Dzięki temu algorytm korzystający z “czegoś co przypomina funkcję” może wyglądać choćby tak:
    template < typename T, typename SearchFunc >
    const T find(const std::vector& v, SearchFunc pred)
    {
    for (int i = 0; i < v.size(); ++i) if (pred(v[i])) return v[i]; // znaleziono element spełniający predykat return T(); }[/cpp] Określenie "coś co przypomina funkcję" jest jak najbardziej na miejscu, gdyż tutaj predykatem może być cokolwiek, co da się jako funkcję potraktować - czyli wywołać operatorem (). Może więc to być zwykły wskaźnik, jakaś ładna zewnętrzna implementacja mechanizmu delegatów (np. FastDelegate) lub jakikolwiek obiekt z przeciążonym operatorem nawiasów (). Właśnie te ostatnie nazywa się zwykle funktorami, a jeśli ktoś nieco bardziej zagłębił się w bibliotekę STL, na pewno nie raz się z nimi spotkał.

Trzeba też powiedzieć, że właściwie istnieje też inny sposób: zamiast samej funkcji przekazywanie jej… nazwy. “I niby jak ją potem wywołać?”, można zapytać. Ano to już indywidualna kwestia każdego języka – w tym przypadku zwykle interpretowanego :)

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

Kwantowanie kierunku

2009-03-13 17:20

Wszyscy wiedzą jak, mając dane dwa punkty, wyznaczyć wektor kierunkowy od pierwszego punktu do drugiego. Niekiedy jednak nie chcemy, aby możliwe było uzyskanie dowolnego kierunku. Może tak być np. przy poruszaniu jednostkami na mapie, gdy z jakiegoś powodu chcemy dopuścić, powiedzmy, tylko 8 czy 16 podstawowych kierunków. W jaki sposób należy wtedy “zaokrąglić” nasz dowolny wektor, uzyskany jako różnica aktualnej pozycji jednostki i np. miejsca kliknięcia myszką przez gracza?

Pierwszym możliwym sposobem jest zamiana jego reprezentacji ze współrzędnych prostokątnych (x, y) na biegunowe (r – długość, theta – kąt między dodatnią półosią X a wektorem). Jest to możliwe przy pomocy obecnej w wielu językach funkcji atan2(y, x). Wystarczy potem sprawdzić, któremu wzorcowemu wektorowi jest najbliższy otrzymany kąt.

Swego czasu znalazłem jednak nieco inny sposób, który daje się zastosować bez zmiany reprezentacji wektora. Oryginalnie służył on do wyboru jednego z ośmiu podstawowych kierunków, ale nietrudno było zauważyć, że da się go trochę uogólnić:

  1. VEC2 Quantize(const VEC2 v, int k)
  2. {
  3.     v.Normalize();
  4.     v *= k;
  5.     return VEC2((int)Round(v.x), (int)Round(v.y));
  6. }

Użyta tutaj funkcja Round(t) oznacza zaokrąglenie w stronę najbliższej liczby całkowitej, czyli floor(t + 0.5). Współczynnik k kontroluje natomiast, ile wektorów wzorcowych znajduje się w naszej “róży wiatrów”. Powyższa funkcja dzieli bowiem kąt pełny na dokładnie 2k+2 wycinków, dając tyle też możliwych wektorów wynikowych. Osiem kierunków otrzymamy więc dla k = 1, szesnaście dla k = 2, itd. Teoretycznie możliwe są też ułamkowe wartości współczynnika, co najprawdopodobniej pozwałoby kontrolować “czułość dopasowania” wektora do wzorca. Nie podjąłem się jednak opracowania jakiejś ścisłej zależności :) Jedyne co udało mi się zaobserwować to to, że dla k = 2/3 otrzymujemy dopasowanie do czterech podstawowych kierunków (N, S, W, E).
Ogólnie więc nie jest to może epokowe odkrycie w dziedzinie wektorologii stosowanej, ale istnieje szansa, że komuś do czegoś się przyda ;]

Tags: , ,
Author: Xion, posted under Programming » Comments Off on Kwantowanie kierunku

volatile?…

2009-02-23 13:18

Modyfikator volatile nie należy do często używanych elementów języka C(++). Jeśli więc gdzieś się go napotka, ma się sporą szansę nie odgadnąć od razu, dlaczego został użyty. Można też samemu przeoczyć sytuacje, gdy należałoby z niego korzystać.
Teoretycznie to słowo kluczowe nie powinno w ogóle istnieć; jest ono “techniczną” częścią języka, związaną ze sposobem jego kompilacji – trochę tak, jak klauzula checked z C# jest ściśle związana z metodami wykonywania obliczeń przez (ko)procesor. Wiemy jednak doskonale, że C++ wysokim poziomem abstrakcji nie grzeszy (już o C nie wspominając), więc obecność takich elementów nie powinna specjalnie dziwić.

volatile jako modyfikator zastosowany do (typu) zmiennej sprawia, że będzie ona traktowana tak, jakby jej zawartość mogła się w każdej chwili zmienić. Inaczej mówiąc, kompilator nie powinien nigdy czynić jakichkolwiek założeń co do wartości takiej zmiennej, bo jej wartość może być w dowolnym momencie przez coś zmodyfikowana.
Tak to wygląda od strony specyfikacji. W praktyce volatile stosuje się głównie w dwóch przypadkach:

  • Po pierwsze, używamy tego słowa jeśli rzeczywiście wartość naszej zmiennej może być zmodyfikowana przez jakiś ‘czynnik zewnętrzny’. Na niektórych maszynach tak na przykład działają urządzenia wejściowe: akcja w rodzaju wciśnięcia klawisza przez użytkownika powoduje zmianę zawartości jakiejś komórki pamięci. Chcąc na nią zareagować, należy więc cały czas monitorować to miejsce, bo może ono zmienić swoją zawartość zupełnie niespodziewanie. Oczywiście teraz takich rozwiązań się już nie stosuje, bo urządzenia wejściowe generują po prostu przerwania (interrupts), które są potem przerabiane przez system operacyjny na odpowiednie zdarzenia.
    Z globalnymi zmiennymi volatile można jednak często się spotkać w programach uniksowych, które funkcjonują w oparciu o sygnały. Typowym przykładem są serwery sieciowe, działające w pętli aż do momentu, gdy im się przerwie:

    1. while (!interrupted) do_work();

    Zmienna z warunku jest wtedy deklarowana jako:

    1. volatile sig_atomic_t interrupted = 0;

    zaś w procedurze obsługi sygnału – która może być wywołana w dowolnym momencie w odpowiedzi na przyjście żądanego sygnału (zwykle SIGINT) – jest ona ustawiana na 1. Gdyby nie była volatile, kompilator uznałby, że zawsze ma ona wartość zerową i “zoptymalizował” powyższą pętlę, zamieniając ją na nieskończoną.

  • Po drugie, z volatile korzysta się wtedy, chcemy w sposób zamierzony zapobiec pewnym optymalizacjom kodu. Zwykle chodzi tutaj o jakieś testowanie szybkości pewnych operacji, np. arytmetycznych. Powinno się wtedy wykonywać je na zmiennych opatrzonych modyfikatorem volatile, żeby mieć pewność, że wszystkie działania się wykonają i żadne nie zostanie wyeliminowane w procesie kompilacji. Można oczywiście wątpić w zdolności optymalizacyjne kompilatora, ale jest całkiem możliwe, że – zgodnie ze sprawdzonym po wielokroć prawem Murphy’ego – włączą się one właśnie tam, gdzie akurat byśmy ich sobie nie życzyli :)

Jeśli więc któryś z tych dwóch powyższych przypadków pasuje do naszej sytuacji, zapewne powinniśmy posłużyć się słowem kluczowym volatile.

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

Funkcje zagnieżdżone i C++

2008-12-30 20:19

Niekiedy przydatna okazuje się możliwość definiowania funkcji widocznych wyłącznie w obrębie innej funkcji – czyli procedur zagnieżdżonych. Używa się tego najczęściej do krótkich, pomocniczych funkcji; oto najprostszy przykład w języku, który to umożliwia (Delphi):
[delphi]// oblicza odległość między dwoma punktami
function Distance(p1, p2 : TPoint) : Double;
function Square(X : Double) : Double;
begin
Result := X * X;
end;
begin
Result := Sqrt(Square(p1.X – p2.X) + Square(p1.Y – p2.Y));
end;[/delphi]
Takim językiem nie jest jednak C++, więc pewnie istnieje ku temu jakiś bardzo ważny powód… Bo czyż nie jest tak z każdą przydatną funkcjonalnością, która została w nim pominięta? ;D
Ale żarty na bok. W C++ można – przy odrobinie pomysłowości – osiągnąć dość podobny efekt:

  1. double Distance(POINT p1, POINT p2)
  2. {
  3.     static class
  4.     {
  5.         public:
  6.             double operator() (double x) const { return x * x; }
  7.     } Square;
  8.  
  9.     return sqrt(Square(p1.X - p2.X) + Square(p1.Y - p2.Y));
  10. }

Nie tworzymy tutaj funkcji, tylko odpowiednio nazwany obiekt anonimowej klasy, któremu przeciążamy operator nawiasów (wywołania funkcji). Efekt na oko jest taki sam: mamy pewną nazwę (Square), którą możemy użyć jak funkcję, lecz nie jest ona widoczna poza macierzystą procedurą (czyli Distance). Nasz obiekt deklarujemy też jako statyczny, dzięki koszt jego tworzenia i niszczenia ponosimy tylko raz, a ponadto nie zajmuje on miejsca na stosie (gdyż w innym przypadku z pewnością zająłby je; standard C++ mówi, że nawet obiekty klas bez zadeklarowanych pól nie mają rozmiaru 0).

Ta sztuczka jest jednak daleka od rzeczywistych funkcji zagnieżdżonych. W “prawdziwym” wydaniu mają one bowiem jedną ważną właściwość: posiadają dostęp do zmiennych lokalnych funkcji, w których są zawarte. W naszym przykładzie “funkcja” Square powinna więc móc odwołać się do (ewentualnych) zmiennych lokalnych z funkcji Distance. A ponieważ Square jest tutaj tak naprawdę obiektem jakiejś klasy, która nic nie wie o Distance, nie jest to rzecz jasna możliwe.
Czy możliwe jest więc, aby pełnowymiarowe funkcje zagnieżdżone pojawiły się np. w przyszłych wersjach języka C++?… Tutaj odpowiedź jest prawie na pewno negatywna. Jest tak dlatego, że obecność takich funkcji ingeruje bardzo głęboko w sposób, w jaki kompilator postępuje ze wszystkimi funkcjami. Pośrednimi konsekwencjami dodania funkcji zagnieżdżonych byłyby: niemożność korzystania ze standardowej konwencji wywoływania cdecl oraz zmiana wewnętrznej struktury wszystkich wskaźników na funkcje (które nie mogłyby być już pojedynczymi adresami).

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

Kolejność na liście inicjalizacynej

2008-11-07 10:40

Jak wiadomo, do konstruktorów w C++ możemy doczepić listy inicjalizacyjne, pozwalające nadawać początkowe wartości polom macierzystej klasy (i nie tylko zresztą). Związany jest z tym pewien pozornie zaskakujący fakt, dotyczący kolejności inicjalizacji tych pól:

  1. class Foo
  2. {
  3.     private: string a, b;
  4.     public: Foo() : b("b"), a("a") { }
  5. };

Są one zawsze ustawiane w porządku zgodnym z ich deklaracjami w klasie. Tak więc powyżej inicjalizowane będzie najpierw pole a, zaś potem b – mimo że w konstruktorze kolejność jest odwrotna. Oczywiście w takim prostym przypadku nie ma to znaczenia, ale jeśli między polami występują zależności, wtedy może to być przyczyną “dziwnych” błędów. Porządniejsze kompilatory ostrzegają na szczęście przed rozbieżnymi kolejnościami pól w klasie i na liście w konstruktorze.

Można naturalnie zapytać, dlaczego w ogóle jest to zorganizowane tak nieintuicyjnie. Pierwsza nasuwająca się odpowiedź – “bo to C++” – nie jest bynajmniej zadowalająca :) Tak naprawdę przyczyną jest to, iż konstruktorów może być naturalnie więcej niż jeden:

  1. public:
  2.     Foo() : b("b"), a("a") { }
  3.     Foo(const Foo& foo) : a(foo.a), b(foo.b) { }

i mogą mieć one różną kolejność pozycji na liście inicjalizacyjnej. Gdyby to ona liczyła się bardziej, wtedy różne obiekty tej samej klasy byłyby konstruowane na różne sposóby. Co gorsza, sposób tej konstrukcji (kolejność inicjalizacji pól) musiałby zostać gdzieś zapamiętany na czas życia obiektu, jako że jego pola powinny być później zniszczone w kolejności odwrotnej do konstrukcji – zgodnie z zasadami języka.
Krótko mówiąc, zastosowanie “intuicyjnego” podejścia skutkowałoby nie tylko znacznie większymi niejasnościami, ale i dodatkowymi kłopotami zarówno dla programisty, jak i kompilatora.

Tags: , ,
Author: Xion, posted under Programming » Comments Off on Kolejność na liście inicjalizacynej
 


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