Badania terenowe nad budowaniem stringów

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:

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

Dziel i rządź… wątki

Na forum Warsztatu – i pewnie na wielu innych forach tego typu – dość często występuje zjawisko, którego przyczyn ciężko mi jest dociec i równie ciężko jest je zrozumieć. Powoduje ono przy tym trochę dodatkowej pracy dla moderatorów, czyli między innymi także i dla mnie.

O co chodzi? O dziwną praktykę “doklejania” swoich pytań do już istniejących wątków. Zazwyczaj zaczyna się od tego, że ktoś przegląda sobie temat, na który udzielono już zadowalających autora odpowiedz. I wtedy pewnie ów ktoś przypomina sobie, że przecież miał/ma podobny problem… Względnie przeczytał cały ten wątek z nadzieją na uzyskanie rozwiązania swojego problemu (bo przecież ma podobny), która to jednak okazała się płonna.
Co wtedy robi ów jegomość? Ano chwyta za wirtualne pióro, żeby podzielić się ze światem swoimi programistycznymi troskami. I nie wiedzieć czemu w większości przypadków robi to, dopisując po prostu nowy post w tym samym wątku. Dlaczego? – to właśnie pytanie od dawna spędza mi sen z powiek…

Dobra, powiedzmy, że trochę koloryzuję ;] Tak naprawdę ludzie zazwyczaj uzasadniają, dlaczego zamiast założenia nowego tematu, dopisują swoje pytania w już istniejącym (co swoją drogą jest wskazówką, iż mają świadomość, że postępują źle). Typowe są tu mianowicie dwa wyjaśnienia.
Po pierwsze: z lenistwa. To paradoksalnie jest ten lepszy powód, a przynajmniej dający się zrozumieć (w końcu teoretycznie założenie nowego wątku to aż kilka kliknięć więcej…). Dodatkowo można też docenić tutaj delikwenta za świadomość posiadania określonych przywar charakteru i gotowością do przyznania się do nich w razie potrzeby. Innymi słowy, wykazuje się on wtedy wielce pożądaną, acz coraz rzadszą w dzisiejszych czasach cnotą szczerości… Tak, w tym przypadku żartuję oczywiście ;P

A jaki jest ten drugi powód? Otóż brzmi on następująco: “Nie zakładam nowego wątku, ażeby nie zaśmiecać forum”. To, jaka pokrętna logika stoi za takim stwierdzeniem, jest dla mnie nierozwiązywalną zagadką. O ile łatwiej byłoby później znaleźć pytanie (i odpowiedź) stanowiące osobny wątek, opatrzony – miejmy nadzieję – adekwatnym tytułem, umieszczony w odpowiednim dziale niż któryś z kolei post numer N na stronie M wątku X, który to oryginalnie dotyczył czegoś innego.
Trzeba też wspomnieć o tym, że podczepianie się pod istniejący temat to zwykła kradzież. Kradnie się bowiem część czasu i uwagi, którą inni forumowicze poświęcili oryginalnemu pytaniu i “przekierowuje” je na nowy problem. Jednocześnie ten pierwotny temat traci szansę na dalsze rozwinięcie – chyba że wciąż będą się pojawiać do niego odpowiedzi i przeplatać z tymi odnoszącymi się do nowego pytania. W rezultacie mamy śmietnik – a podobno tego właśnie chcieliśmy uniknąć.

W regulaminie forum Warsztatu znajduje się stosowny punkt, odradzający tego typu praktyk. A mimo to moderatorzy nie walą za nie po łapach banami, nie kasują takich wtrąconych pytań, tylko pracowicie dzielą te wątki na dwie części – bynajmniej nie usuwając tych nowych. I jak tu teraz mówić, że jesteśmy surowi i źli? ;)

LINQ bywa przydatny

Wśród feature‘ów wprowadzonych w wersji 3.5 frameworka .NET jest między innymi LINQ (Language INtegrated Query). Mechanizm ten umożliwia – w dużym skrócie rzecz jasna – konstruowanie zapytań odnoszących się do kolekcji obiektów (w zasadzie dowolnego rodzaju) przy pomocy operatorów znanych z relacyjnych baz danych, jak SELECT czy WHERE. Ponadto w .NET 3.5 język C# został też odpowiednio rozszerzony, aby zapytania ta składniowo mogły przypominać kwerendy podobne do tych występujących w różnych odmianach języka SQL.

“A po co to komu?”, można zapytać od razu i nie ukrywam, że moja reakcja na LINQ była podobna. W końcu kto by chciał zaśmiecać taki ładny język jak C# zupełnie nieprzydatnym nikomu SQL-em? ;] Poza tym mówimy tutaj o czymś trochę z innej bajki, bowiem języki zapytań różnią się od języków programowania tym, że są deklaratywne: pisanie w nich polega na określeniu, co chcemy otrzymać – nie zaś tego, co po kolei program ma robić. (Jak nietrudno się domyślić, ogranicza to trochę stosowalność takich języków). Czemu więc chce się te dwie rzeczy połączyć?…

Odpowiedź jest jak zwykle dość prosta: dla wygody. Za pomocą LINQ nie zrobi się niczego nowego, ale pewne operacje można wykonywać prościej. Czasami można sobie oszczędzić dodatkowych pętli i zmiennych lokalnych – jak chociażby w poniższym przykładzie, w którym chcemy pobrać wszystkie wartości zaznaczone na liście z polami wyboru (check box list) i coś z nimi zrobić:

Można się oczywiście spierać, która wersja jest czytelniejsza i którą jest łatwiej/szybciej napisać. To jednak jest w dużym stopniu kwestią subiektywną. Jak dla mnie możliwość uniknięcia kolejnej pętli, która udaje, że coś robi (a tak naprawdę tylko przerzuca dane z jednego miejsca w inne) jest całkowicie zadowalająca.
Przy bardziej skomplikowanych przypadkach miałbym aczkolwiek dużo większe możliwości. Jest oczywiście możliwe pisanie błyskotliwych kwerend przemiatających po cztery pojemniki naraz i używających takich operatorów jak group czy orderby, by zrobić w trzech linijkach zapytania to, co inaczej wymagałoby 20 wierszy kodu. Sęk w tym, że prawdopodobnie odczytanie znaczenia tych 20 wierszy byłoby wówczas znacząco łatwiejsze ;P

Sortowanie dla zaawansowanych

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 ;]

Podłączanie debugera VS do procesu

Kiedy piszemy aplikację będącą już w na tyle zaawansowanym stadium, że nie objawia ona błędów przy pierwszym lepszym uruchomieniu, to zdarza się, iż uruchamiamy ją bez wsparcia debugera (co można zrobić standardowym skrótem klawiszowym Ctrl+F5 w Visual Studio). Mimo tego zawsze może się jednak zdarzyć jakiś nieprzewidziany wyjątek, błąd czy inna nieprawidłowość. Ba, może się tak zdarzyć w programie, który już dawno uznaliśmy za skończony!
Co wtedy? Przecież warunki powstania błędu mogą być trudne i pracochłonne do odtworzenia, jeślibyśmy uruchomili program ponownie – już w trybie debugowania. Nierzadko zresztą po takiej próbie błąd nagle w “magiczny” sposób zniknie, bo okaże się, że albo coś przeoczyliśmy, albo dany bug zależy od jakichś nieznanych jeszcze okoliczności, albo że całkiem niedeterministyczny (heisenbug).

Dlatego też lepiej posłużyć się już tą instancją programu, w której problem wystąpił, i przy jej pomocy poszukać błędu. W tym celu można użyć przydatnej opcji Visual Studio, pozwalającej na przyłączenie debugera do działającego procesu i dostępnej poprzez menu Debug > Attach to Process. Tam możemy wybrać po prostu naszą aplikację z listy działających procesów.
Jakie możliwości nam to daje? To zależy od tego, czy w pliku wykonywalnym docelowej aplikacji znajdują się odpowiednie symbole debugowe . W najlepszym wypadku będziemy mogli śledzić kod programu tak samo, jak przy uruchamianiu go z asystą debugera od samego początku (o ile, rzecz jasna, wcześniej otworzymy projekt, z którego kompilowaliśmy nasz program). Jeśli zaś nie dysponujemy źródłem aplikacji lub docelowy plik .exe nie posiada żadnych symboli debugowych, to oczywiście nadal możemy wykonywać działania typowe dla każdego debugera – jak krokowe wykonywanie instrukcji maszynowych czy ustawianie breakpointów na konkretnych adresach w pamięci.

O klasie Convert

Stawiając pierwsze kroki w programowaniu w C#/.NET, można odkryć kilka ciekawych właściwości, które nie zawsze występują w innych językach. Jednym z nich jest całkiem dobre rozwiązanie odwiecznego problemu w kodowaniu, czyli zamiany między różnymi typami danych: zwłaszcza do i z łańcucha znaków.
Przykładem jest chociażby metoda ToString, która zrobi nam napis z dowolnego obiektu. Są też metody w stylu int.Parse, które potrafią odczytać liczbę zapisaną jako tekst i w zgrabny sposób rozwiązują jeden z najpowszechniejszych kłopotów wszystkich początkujących programistów :) (O ile oczywiście pomyślą oni o tym, że typ bądź co bądź, podstawowy, może mieć metody tak, jak klasa). W końcu, jest też rzutowanie; może ono służyć do “przywrócenia” właściwego typu obiektu, o którym z jakichś powodów “zapomnieliśmy”, ale również do konwersji między typami podstawowymi.

W sumie więc mechanizmów tego rodzaju jest dość dużo. Co więcej, nietrudno też – zwłaszcza w rzeczywistych, a nie przykładowych kodach – natrafić na jeszcze jeden. Jest to mianowicie użycie statycznej klasy Convert, zawierającej kilka metod typu ToDouble lub ToBoolean. I wydaje się, że korzystanie właśnie z niej najbardziej się opłaca. Dlaczego?
Ano głównie ze względu na jej uniwersalność – można z niej korzystać właściwie do wszystkich konwersji wyliczonych wyżej, i nie tylko. Daje to kod czytelniejszy, w którym od razu widać, co chcieliśmy zrobić – zwłaszcza jeśli alternatywą jest pokrętne obejście w rodzaju pośredniej konwersji do stringa. Ponadto klasa ta bywa sprytniejsza niż podane wcześniej sposoby, radząc sobie chociażby z typami danych używanymi przez API dostępu do baz danych (np. SqlInt32) i przerabiając je na bardziej użyteczne wartości.

W końcu, nie da się też ukryć, że korzystanie z mniej znanej, ale za to jakże wyspecjalizowanej klasy do prostych czynności jest niewątpliwą oznaką dużego profesjonalizmu… czyż nie? ;] I to pewnie jest najważniejszy argument ‘za’ ;P

Boost i liczby losowe

Narzekanie na jakość generatorów liczb (pseudo)losowych wbudowanych w języki programowania (takich jak rand() w C/C++) to dość popularne zajęcie wśród programistów gier. Chociaż nierzadko jest ono raczej bezpodstawne (albo ma charakter martwienia się na zapas), to niekiedy faktycznie losowość (czy raczej: nieregularność) uzyskiwanych wyników pozostawia wiele do życzenia.
Oczywiście zagadnienie generowania liczb “losowych” doczekało się mnóstwa opracowań jeszcze na długo przed tym, zanim stały się one potrzebne do wyliczania ruchu piłeczki odbitej od paletki w Pongu :) W praktyce możemy więc znaleźć mnóstwo dobrze działających implementacji różnego rodzaju generatorów liczb pseudolosowych dla większości znanych we Wszechświecie języków programowania.

Wspominam o tym, bo ostatnio sam potrzebowałem czegoś podobnego w C++. A gdzie zagląda każdy programista tego języka, gdy czegoś mu brakuje?… Do Boosta naturalnie :) Jako że jest tam (prawie) wszystko, niespecjalnie zdziwiło mnie, że istnieje cała biblioteka od szeroko pojętej losowości – Boost.Random. Zawiera ona rzecz jasna implementacje kilku różnych generatorów liczb pseudolosowych, różniących się nieregularnością wyników, szybkością, wymaganiami pamięciowymi, itd.
Tak naprawdę jednak tym, co czyni tę bibliotekę interesującą, jest sposób łączenia tych generatorów z wieloma dostępnymi tam rozkładami liczb losowych. Jeśli ktoś przysypiał na lekcjach matematyki lub wykładach z rachunku prawdopodobieństwa, to przypomnę, że – najprościej mówiąc – rozkład określa nam, jakie wartości mogą być wylosowane i jakie jest prawdopodobieństwo uzyskania każdej z nich. Przykładowo, standardowy rand teoretycznie oferuje nam liczby losowe o rozkładzie jednorodnym na zbiorze { 0, 1, …, RAND_MAX-1 }. Oznacza to, że – gdyby losowość była tu rzeczywista, a nie udawana – każda z tych wartości ma taką samą szansę na bycie wylosowaną. W przypadków innych rodzajów rozkładów nie musi tak być i niektóre wyniki mogą być bardziej preferowane niż inne (niezależnie od jakości generatora).

Jak więc wygląda to w Boost.Random? Ano całkiem zgrabnie. Najpierw bowiem wybieramy używany generator liczb, a potem pożądany rozkład, i obie te rzeczy możemy połączyć w jeden poręczny obiekt. Oto przykład:
#include

// generator liczb losowych
// (jest to pewna wersja znanego algorytmu Mersenne Twister)
boost::mt19937 rng;

// docelowy rozkład otrzymywanych liczb
// (jednorodny rzeczywisty na przedziale -1…1)
boost::uniform_real dist(-1, 1);

// wynikowy obiekt
boost::variate_generator >
random(rng, dist);

// kilka losowań
for (int i = 0; i < 10; ++i) std::cout << random() << std::endl;[/cpp] Jak nietrudno zauważyć, ten przykład pokazuje, jak bardzo C++ potrzebuje obecnego w C# od wersji 3.0 słowa kluczowego var ;-) Poza tym jednak widzimy, że otrzymany obiekt jest w użyciu bardzo prosty: aby dostać następną losową liczbę, wystarczy po prostu użyć na nim operatora (). Rezultat będzie od razu z właściwego przedziału (nie trzeba żadnych mnożeń czy dzieleń modulo), który określamy, definiując rozkład. Tutaj jest on jednorodny, ale oczywiście w Boost.Random mamy też mnóstwo innych, jak choćby geometryczny, wykładniczy, Gaussa (normalny), Bernoulliego, itp.
Nie to żeby były one jakoś często potrzebne, ale kiedy trafi się – tak jak mi – konieczność użycia któregoś z nich, to dobrze jest mieć tę bibliotekę pod ręką :)