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 &lt. 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:

    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 <boost/random.hpp>

// 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<float> dist(-1, 1);

// wynikowy obiekt
boost::variate_generator<boost::mt199937&, boost::uniform_real<float>>
   random(rng, dist);

// kilka losowań
for (int i = 0; i <10; ++i)    std::cout <<random() <<std::endl;

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



Płaska wizualizacja funkcji 3D

Funkcje, których dziedziną jest podzbiór R2 (czyli płaszczyzna) ciężko jest przedstawić na płaskim ekranie w sposób poglądowy, a jednocześnie pozwalający na odczytanie jakichś wartości. O ile bowiem izometryczny rzut 3D wygląda efektownie, to poza ogólnym kształtem powierzchni nie przedstawia wielkiej ilości informacji. Sprawa wygląda trochę lepiej, jeśli taką figurę możemy jeszcze obracać... co aczkolwiek może być z kolei trudne do zrealizowania np. na wydruku :]

Jednym z wyjść może być tutaj zastosowanie sposobu używanego do map wysokości w grach. Nietrudno zauważyć, że są one niczym innym jak właśnie funkcjami typu R2->R, a reprezentowane są najczęściej jako bitmapy w odcieniach szarości: jasność piksela x,y odpowiada w nich wysokości odpowiedniego punktu terenu.
Takie heightmapy wprawdzie łatwo się rysuje, ale niespecjalnie nadają się do pokazania jako ilustracja czegokolwiek - odcienie szarości są przecież z definicji szare i nieciekawe :) Dlatego bardzo spodobał mi się prosty pomysł na uczynienie tej reprezentacji znacznie ładniejszą, o którym to usłyszałem niedawno.

Idea jest prosta: po co używać samych szarości, skoro mamy do dyspozycji całą paletę kolorów?... Każdy kolor w reprezentacji RGB jest przecież tożsamy z liczbą, co widać najbardziej, jeśli weźmiemy jego typową reprezentację 32-bitową:

W niej "największym" kolorem jest kolor biały (0x00FFFFFF, czyli 224 - 1), zaś "najmniejszym" czarny (0x0), a pomiędzy nimi włącznie występuje każdy z 2563 możliwych kolorów. Jeśli teraz przeskalujemy wartości naszej funkcji do tak określonego przedziału (lub nieco mniejszego), a następnie przekonwertujemy każdą z tych 32-(a właściwie 24-)bitowych liczb na odpowiadający jej kolor RGB, to otrzymamy w ten sposób heightmapę o znacznie bogatszej palecie barw niż poprzednio.
Jeśli ponadto używamy dokładnie takiej reprezentacji liczbowej kolorów, jak powyżej (najmłodsze bity na kolor niebieskie, a najstarsze używane na czerwony), to zauważymy, że rozkład barw w wyniku jest całkiem znajomy. I tak obszary niebieskie odpowiadają wartościom najmniejszym, zielone średnim, żółte - wysokim, a czerwone - najwyższym. Łącznie przypomina mapę hipsometryczną - czyli, jakby nie patrzył, mapę wysokości właśnie :)

Do czego może przydać się takie cudo, oprócz wspomnianej już wizualizacji funkcji R2->R na płaszczyźnie? Pewnie do niewielu rzeczy :) Ja wpadłem jednak na jeszcze jedno potencjalne zastosowanie.
Ponieważ wynikowy obrazek używa tak "geograficznych" barw, może on całkiem dobrze wyglądać jako... tło minimapy pokazywanej w grze, która rozgrywa się na terenie opisanym mapą wysokości. Oczywiście rzecz wymagałaby dopracowania: przede wszystkim bardziej starannego dobrania kolorów brzegowych (niekoniecznie białego i czarnego) oraz być może kolorów pośrednich (np. kolor poziomu morza), a i pewnie zastosowania jakichś filtrów na wynikowym obrazku (np. wygładzania). Efekty mogłyby być jednak interesujące, co widać obok.



Funkcje jako dane wejściowe

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:
    // sortowanie listy w oparciu o własny predykat (C# 2.0 wzwyż)
    objects.Sort (delegate (object a, object b)
        { 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<T>& 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();
        }

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



Podwójne skróty klawiszowe w VS

W takiej dużej aplikacji jak IDE ilość opcji jest na tyle spora, że część z nich pochowana jest głęboko w czeluściach wielopoziomowego menu. Często nie znaczy to jednak, że są one mniej przydatne; na pewno jednak są trudniej dostępne. Dodatkowo też ilość klawiszy na klawiaturze jest ograniczona, więc nie wszystkie opcje mogą mieć przypisane skróty klawiszowe... Chyba że zastosuje się jakieś sztuczkę :)

W vimie i jego pochodnych taką sztuczką były polecenia wpisywane od dwukropka (na czele z najbardziej przydatnym, czyli :q! ;]). W Visual Studio mamy za to podwójne skróty klawiszowe, (chords) dzięki którym możemy z palca wywołać nie tylko, powiedzmy, polecenie otwarcia pliku, ale też pewne rzadziej używane narzędzia - które paradoksalnie bywają o wiele przydatniejsze.
Jak to działa? Otóż bardzo prosto: po wciśnięciu specjalnej kombinacji 'aktywującej' (np. Ctrl + K) nic się wprawdzie nie dzieje, ale aplikacji przełącza się w tryb pozwalający na wykrycie drugiej kombinacji (np. Ctrl + C), która odpowiada już konkretnej akcji. Całość można więc zapisać jako Ctrl + K,C; oznacza to po prostu: wciśnij i przytrzymaj Ctrl, a potem naciśnij kolejno K i C. Nic specjalnie trudnego, prawda? :)

A jakież to wspaniałe opcje IDE są dostępne w ten sposób? Ano jest ich całkiem sporo, spośród których wylistuję kilka:

  1. Komentowanie kodu. Tak tak, nie trzeba już ręcznie wstawiać /* */ czy #if 0/#endif, żeby wyłączyć jakiś kawałek kodu z kompilacji :) Mamy bowiem takie oto skróty:
    • Ctrl + K,C - komentuje (w stylu C++) każdą linijkę zaznaczonego fragmentu
    • Ctrl + K,U - odkomentowuje zaznaczony fragment (usuwa // z początku każdej linijki)
  2. Edycja kodu:
    • Ctrl + K,X - pozwala na wstawienie predefiniowanych wzorców (snippets) różnych konstrukcji językowych (np. pętli for), pozwalając przy tym na łatwą zmianę ich szczegółów (np. nazwy zmiennej będącej licznikiem pętli).
    • Ctrl + K,S - pozwala otoczyć zaznaczony fragment kodu jakimś nazwanym blokiem, np. try-catch, if, itd.
  3. (Ro)zwijanie bloków. W VS bloki kodu mogą być rozwijane lub ukrywane poprzez klikanie w mały plusik z lewej strony ich pierwszego wiersza. Opcja ta nazywa się outlining lub folding i można ją kontrolować m.in. przy pomocy poniższych skrótów:
    • Ctrl + M,O - zwija wszystkie bloki tak, że widoczne są tylko nagłówki definicji funkcji i metod
    • Ctrl + M,L - (ro)zwija wszystkie bloki
    • Ctrl + M,P - wyłącza automatyczny outlining całkowicie
  4. Zmiana sposobu przeglądania kodu:
    • Ctrl + R,W - w(y)łącza wyświetlanie białych znaków (spacji jako kropek, tabulatorów jako strzałek, itd.)
    • Ctrl + E,W - w(y)łącza zawijanie wierszy

Polecam przynajmniej jednokrotne spróbowanie każdej z powyższych opcji. Możliwe, że w ten sposób odkryjecie coś, czego brakowało wam przez cały czas :) Nie jest to też kompletna lista - więcej skrótów/opcji można znaleźć przeglądając menu Edit.