Rozmiar a pojemność

Od kiedy w Bibliotece Standardowej języka C++ istnieje szablon vector, nie trzeba się już martwić kłopotami z dynamiczną alokacją pamięci dla tablic o zmiennym rozmiarze. Szablon ten jest na tyle sprytny, że zapewnia wszystkie zalety zwykłych tablic - łącznie z możliwością uzyskania wskaźnika na ciągły obszar pamięci zawierający elementy. Jednocześnie sam kontroluje rozmiar tablicy oraz wykorzystanie pamięci.
W sensownej implementacji STL jest to osiągnięte poprzez strukturę samorozszerzalnej tablicy. W skrócie można to określić jako alokację większej ilości pamięci niż faktycznie potrzeba - po to, aby dodawanie nowego elementu trwało w przybliżeniu czas stały (w tzw. sensie zamortyzowanym). Całkowita ilość pamięci wykorzystywana aktualnie przez wektor to jego pojemność i jest ona możliwa do pobrania metodą capacity (zwraca ona liczbę elementów, które jeszcze się zmieszczą bez realokacji). Natomiast metoda size zwraca liczbę aktualnie zawartych w tablicy obiektów, czyli jej rozmiar.
Istotne jest, aby te dwie wartości rozróżniać. Kiedy zaś zrównają się ze sobą, następne dodanie elementu wymusi ponowną alokację bloku pamięci dla całej tablicy (zwykle dwukrotnie większego) i przekopiowanie jej zawartości w nowe miejsce.

Taka operacja jest oczywiście kosztowna (liniowa względem rozmiaru tablicy) i dlatego chcielibyśmy, żeby odbywała się jak najrzadziej. Używając metody reserve możemy naraz zaalokować pamięć na tyle elementów, ile będziemy potrzebowali - a więc zwiększyć jej pojemność (lecz nie rozmiar!), jak to widać na poniższym mało inteligentnym przykładzie:

Warto wiedzieć, że pojemność wektora nigdy się sama z siebie nie zmniejszy. Jeżeli więc kiedyś zawierał on 1000 elementów, a obecnie tylko 10, to i tak w pamięci zajmie on miejsce potrzebne na przechowanie tego tysiąca. Nie ma też żadnej metody do "obcinania" nadmiarowej pojemności. Można jednak posłużyć się pewną sztuczką:

Tworzymy tutaj kopię wektora, używając konstruktora kopiującego. Trik polega na tym, że w czasie tworzenia tej kopii zostanie przydzielona dokładnie taka ilość pamięci, jaka jest potrzebna dla elementów wektora. Potem jeszcze zamieniamy ten chwilowy wektor z oryginalnym... i już :)

Najrzadsze słowo kluczowe

Standardowy C++ ma ponad 50 podstawowych słów kluczowych. To naprawdę całkiem sporo, chociaż nowsze języki wykazują jeszcze większą tendencję do produkowania tych elementów składni. Te kilkadziesiąt na razie jednak wystarcza w zupełności. Oczywiście są sytuacje, w których dla przejrzystości przydałoby się dodatkowe słówko (jak na przykład coś podobnego abstract przy deklarowaniu metod czysto wirtualnych). Jeśli jednak nie jesteśmy specjalistami od C++, to może nam się przytrafić spotkanie z keywordem, którego nigdy wcześniej na oczy nie oglądaliśmy.

Dla mnie - i podejrzewam, że nie tylko dla mnie - ostatnim takim przypadkiem było ujrzenie tajemniczego słowa kluczowego mutable. Być może nie jest ono, jak tutaj sugeruję, najrzadziej używanym słowem kluczowym C++ w ogóle, ale jestem przekonany, że mieści się ono co najmniej w pierwsze trójce. A skoro już o nim wspominam, to wypadałoby wyjaśnić, do czego ono służy.
mutable jest mianowicie modyfikatorem, którym możemy opatrzyć pole klasy - na podobnej zasadzie jak np. static czy const (z którymi zresztą mutable wzajemnie się wyklucza). Pole posiadające taki atrybut może być następnie modyfikowane z poziomu każdej metody swojej klasy - włącznie z tymi metodami, które są zadeklarowane jako stałe (const).
Imponujące? Bynajmniej. Mówiąc mniej formalnie, mutable pozwala na to, by obiekt mógł być stały pod względem koncepcyjnym nawet jeśli z pewnych "technicznych" powodów musimy zmienić zawartość niektórych jego pól. C++ jest pedantyczny i traktuje każdą modyfikację wartości składowych obiektu jako niedozwoloną w metodzie stałej. Czasami jednak chcemy tak zrobić, jako że dla nas obiekt ten nadal będzie niezmieniony - mimo tego, iż ze ścisłego, bitowego punktu widzenia zostanie on zmodyfikowany.

Taka sytuacja może zajść na przykład wtedy, gdy pewne dane chcemy wyliczać na żądanie - wtedy, kiedy będą potrzebne. Żeby przykład był życiowy, weźmy element trójwymiarowej sceny, któremu przypiszemy macierz translacji, skalowania i obrotu. W pewnym momencie będziemy chcieli je przemnożyć i dostać macierz całej transformacji, ale nie opłaca się tego robić za każdym razem, gdy zmienia się któraś z macierzy składowych. Jednak metoda zwracająca nam iloczyn powinno zasadniczo być stała, co przeszkadza cacheowaniu tegoż iloczynu jako pola w obiekcie.
I tutaj z pomocą przychodzi nam mutable:

W ten sposób mamy za darmo elegancję, szybkość i spójność koncepcyjną. Znajomość egzotycznych elementów języka może więc wbrew pozorom przynosić czasem konkretne korzyści :)

PS. Jak widać, ten element jest na tyle egzotyczny, że nawet skrypt kolorujący składnię C++ nie potrafi sobie z nim poradzić ;-)

Różne rodzaje książek koderskich

Programowanie to nie tylko ciągłe stukanie w klawiaturę i pisanie kilometrowych listingów (względnie intensywne wyklikiwanie interfejsu użytkownika). Zawsze od czasu do czasu przychodzi czas, gdy trzeba się odwołać do źródła wiedzy fachowej. Na pierwszej linii frontu stoi wtedy zwykle dokumentacja do konkretnego środowiska czy języka, ale nie jest to jedyne źródło wiedzy, z którego programista korzysta. Wśród nich są również książki.

Literatura programistyczna jest naturalnie niezwykle bogata i dotyczy każdego pola koderskiej działalności, wszystkich możliwych bibliotek, języków, metodologii i wszelkich innych aspektów programowania. W takiej klasyfikacji nietrudno się odnaleźć i zazwyczaj łatwo możemy stwierdzić, o czym dana pozycja traktuje. Trochę gorzej bywa z oceną, jak dany temat został w tej konkretnej książce potraktowany.
Jako że przydarzyło mi się przeczytać dość sporą liczbę programistycznych książek, a jeszcze większą - mniej lub bardziej pobieżnie przekartkować, mogę chyba pokusić się o klasyfikację na podstawie tego drugiego, mniej widocznego kryterium. Uważam zatem, że możemy wyróżnić kilka rodzajów książek programistycznych:

• Kompletne omówienia, czyli - nie bójmy się użyć tego słowa - wykłady. Takie książki nie muszą mieć oczywiście arcyporywającego stylu, charakteryzującego większość podręczników akademickich. Wręcz przeciwnie, mogą być napisane w sposób żywy, wciągający i intrygujący. Ich naczelną cechą jest to, że koncentrując się na danym temacie opisują go w sposób dokładny, obszerny i uporządkowany. Kolejne rozdziały przedstawiają poszczególne zagadnienia, pełne są omówień, przykładów, czasem dygresji. To coś w rodzaju koderskiej beletrystyki, dobrej do czytania w wolnych chwilach i do nauki zupełnie nowych treści.
• Książki kucharskie. Jak sama ich nazwa wskazuje, zawierają one przepisy (czasem zwane wręcz recepturami) na mniej lub bardziej konkretne rozwiązania praktycznych problemów. Mogą to być kompletne sposoby na realizację jakichś fragmentów programu albo tylko artykuły sygnalizujące istnienie pewnych narzędzi i metodyk. Zawsze jednak zakładają pewną wiedzę czytelnika w danym temacie, co nie przeszkadza im jednocześnie wyłożyć przy okazji jakichś drobnych fragmentów obszerniejszych zagadnień. Najważniejsze jest jednak to, że są one skoncentrowane na praktycznym wykorzystaniu zawartych w nich "sztuczek".
• Notatki z pola bitwy to bardzo ciekawy typ książek, z którymi zetknąłem się dopiero niedawno. W założeniu mają one umożliwić "zaglądanie do warsztatu" doświadczonego programisty i stanowią luźny (lecz uporządkowany) zbiór uwag, fragmentów kodu i komentarzy, tyczących się jakiegoś zagadnienia - zwykle języka, biblioteki lub technologii. Ich celem jest przekazanie wiedzy maksymalnie praktycznej i jednocześnie obszernej. Wymagają dobrego przygotowania ze strony czytelnika, lecz jeśli spełnia on wymagania, może on zyskać nie tylko przydatne informacje, ale i bardzo użyteczne umiejętności.
• Leksykony i materiały referencyjne. Te pozycje mają najwięcej wspólnego z klasyczną, elektroniczną dokumentacją. Systematyczny opis funkcji, klas, właściwości, pól, metod, wyjątków, sygnałów, interfejsów i wszystkich tych elementów, które składają się na dane narzędzie programistyczne. Te grube książki najlepiej jest trzymać na biurku w trakcie pisania kodu. Ich przewaga nad dokumentacją polega zwykle na trafnych przykładach zastosowań opisywanych elementów i lepszą organizacją treści.
• Ciekawostki okołokoderskie. W tych książkach możemy znaleźć właściwie wszystko: od przykładów najczęściej popełnianych błędów po wskazówki, w jaki sposób należy czytać kod napisany przez innych. Jeśli wpadnie nam w ręce któraś z tego rodzaju książek, zwykle albo ją pokochamy i będziemy co jakiś czas do niej wracać, albo uznamy pomysł jej napisania za zupełnie nietrafiony i szybko o niej zapomnimy. Nie muszę chyba wspominać, że systematyczne ułożenie wiedzy i orientacja na teorię/praktykę nie są kategoriami, których powinniśmy używać do oceniania takich książek. W większości jest to bowiem całkowity freestyle - z różnymi skutkami, oczywiście.

Jak w każdej arbitralnej klasyfikacji, także i tutaj szufladki te są rzecz jasna rozmyte i wiele książek zmieściłoby się bez problemu na kilku półkach. Prawdopodobnie takie właśnie są najlepsze i najbardziej użyteczne. W końcu skoro już decydujemy się na treści zapisane na papierze, powinniśmy dążyć do korzystania z nich na wiele sposobów... ;]

Standard i Visual C++ 2005

Zainspirowany pewnym wątkiem na forum Warsztatu, traktującym o rzekomych poważnych niezgodnościach między standardem C++ a kompilatorem zawartym w MS Visual C++ 2005, postanowiłem nieco dogłębniej zbadać tę sprawę. Jak dotąd z owych niezgodności kojarzyłem tylko brak wsparcia dla szablonów eksportowanych - czyli "magicznego" słówka export, pozwalającego na rozdzielanie kodu szablonowego na pliki nagłówkowe i pliki .cpp tak samo, jak zwykłego. Nie jest to zresztą wielkie wykroczenie, jako że kompilatory wspierające szablony eksportowane można pewnie policzyć na palcach jednej ręki, a sam mechanizm też nie należy do szeroko znanych.

Co z innymi niezgodnościami? Odwołanie do dokumentacji Visual C++ przynosi ich jeszcze kilka. Z ciekawszych - oprócz braku obsługi słowa export, o którym już wspomniałem - mogę wymienić:

• Ułomność preprocesorowego operatora # (tzw. łańcuchującego - stringizing operator), który zawiedzie, jeśli zastosujemy go względem stałej napisowej zawierającej sekwencje ucieczki (ciągi rozpoczynające się od znaku backslash: \n, \t, itd.).
• Możliwość, że obiekty nie posiadające żadnych pól będą dzieliły miejsce w pamięci (którego i tak nie zajmują) z innymi obiektami. Standard C++ wymaga natomiast, żeby każdy obiekt miał unikalną lokalizację w pamięci operacyjnej w trakcie całego swojego istnienia (obiektu, nie standardu C++ ;]).
• Brak wykorzystania specyfikacji wyjątków (instrukcji throw (typ_wyjątku)). Innymi słowy, w Visual C++ nie sprawdza się, czy funkcja wyrzuciła wyjątek takiego samego typu, który wcześniej został w niej zadeklarowany.
• Pewne ograniczenia liczbowe, jak choćby: liczbę poziomów zagnieżdżenia bloków kodu (VC++ obsługuje 64, standard rekomenduje 256), kwalifikatorów dostępu dla jednej nazwy (127 zamiast 256) czy parametrów szablonu (64 przeciwko 1024).

I to mniej więcej tyle. Być może kogoś zmartwi brak możliwości napisania algorytmu ze 100 zagnieżdżonymi pętlami lub szablonu z tyloma parametrami, ale osobiście mam co do tego pewne wątpliwości :)

Całkiem proste krzywe

W grafice dąży się do tego, żeby rezultat był ładny. Jest to rzecz jasna pojęcie bardzo względne, ale wiadomo na przykład, że kształty opływowe są generalnie lepiej postrzegane niż kanciate. W projektowaniu królują więc linie krzywe, a jednym z ich rodzajów są krzywe wielomianowe stopnia trzeciego, zwane też kubicznymi.

Jak ich nazwa wskazuje, są one opisane wielomianami stopnia trzeciego, czyli ich równania parametryczne zawierają współczynniki w trzeciej potędze. Taki stopień wystarcza, by krzywe te były wystarczająco gładkie (zarówno w rozumieniu matematycznych - ciągłość pochodnych - jak i zwyczajnie "na oko"), a jednocześnie niezbyt kosztowne obliczeniowo. Ponadto można dla nich relatywnie łatwo określić zależność między poszczególnymi czterema parametrami a kształtem wynikowej figury.
To jednak zależy od tego, jaką reprezentację przyjmiemy. Mającą najciekawsze własności i pewnie najpopularniejszą jest reprezentacja Béziera, stworzona przez pewnego włoskiego inżyniera w latach 60. ubiegłego stulecia. Mogę przypuszczać, że niemal każdy średnio zorientowany programista czy grafik słyszał o tego rodzaju krzywych - chociażby dlatego, że narzędzie Krzywa w Paincie jest właśnie krzywą Béziera ;) Spotyka się je też zresztą w bardzo wielu miejscach, łącznie z tekstem (czcionki TrueType są opisane takimi właśnie splajnami).

Dlaczego?... Jak wiadomo, krzywa trzeciego stopnia w postaci Béziera jest opisana czterema punktami: początkiem, końcem oraz dwoma punktami kontrolnymi, których położenie determinuje kształt krzywej. Współrzędne tych czterech punktów można podstawić do równania parametrycznego i dla wartości parametru przebiegających od 0 do 1 wyliczyć dowolny punkt leżący na krzywej.
W praktyce ta reprezentacja ma kilka zalet:

• Dobrze widać, w jaki sposób położenie punktów kontrolnych wpływa na kształt krzywej. Wystarczy przez chwilę pobawić się choćby wspomnianym narzędziem z programu Paint, by zobaczyć, że punkty te dość intuicyjny sposób "wyciągają" krzywą, której kształt jest jakby wypadkową przyciągania dwóch "sił".
• Można dokładnie określić wielokąt otaczający krzywą: jest to czworokąt opisany na czterech punktach, które ją definiują. To oczywiście przydaje się do różnego rodzaju przycinania.
• Aby przekształcić krzywą Béziera poprzez translację, obrót lub skalowanie, wystarczy przekształcić opisujące ją punkty. Taka transformacja jest więc bardzo tania, zwłaszcza w porównaniu z przekształcaniem każdego z wielu punktów, których użylibyśmy do przybliżania naszej krzywej.
• Łatwo jest też sklejać krzywe Béziera za sobą, zachowując w punktach połączeń nie tylko ciągłość, ale również w miarę potrzeby gładkość taką samą, jak na całej długości sklejanych krzywych.

Krzywą Béziera można także w miarę szybko narysować, jako że przy stałym (i małym) kroku dla parametru równania przybliżone wyliczanie kolejnych punktów wymaga tylko dodawań. To aczkolwiek cecha wszystkich krzywych wielomianowych, podobnie też jak jedna z ich wad: niemożność dokładnego odwzorowania okręgu. W praktyce gdy ogranicza nasz rozdzielczość pikselowa, taka niedokładność nie jest jednak zbytnim problemem.

Tak więc krzywe Béziera są obecnie prawdopodobnie najlepszym sposobem reprezentowania linii krzywych zarówno na płaszczyźnie, jak i w przestrzeni. Ale oczywiście w przestrzeni trójwymiarowej moglibyśmy chcieć zobaczyć coś więcej, na przykład... płaty Béziera :) To już jednak temat na inną okazję. Na razie mogliśmy się przekonać, że wersje dwuwymiarowe są, jak na krzywe, całkiem proste ;]

Przydatne ułatwienia dostępu

Ponieważ nowoczesne systemy operacyjne - takie jak Windows - starają się być przyjazne dla wszystkich użytkowników, już od dawna wyposażone są w specjalne funkcje ułatwiające korzystanie z komputera osobom z różnymi rodzajami niepełnosprawności. Jest więc możliwość ustawienia większego kontrastu interfejsu użytkownika, włączenia śladu po kursorze, łatwiejszego wciskania skrótów klawiaturowych, i tak dalej.

Chociaż większość tych możliwości zdaje się być przeznaczona wyłącznie dla wspomnianych użytkowników, to jednak przynajmniej dwie mogą być użyteczne dla wszystkich korzystających z Windows. Osobiście znam i często korzystam z dwóch takich, a mianowicie:

• Wyświetlanie podkreśleń dla skrótów klawiaturowych w menu - takich jak np. Plik czy Wklej. Dawniej podkreślanie to było domyślnie włączone, ale ktoś pewnie kiedyś uznał, że psuje ono wygląd interfejsu i że w zasadzie nikt już klawiatury nie używa ;P Naturalnie jest to przekonanie całkowicie błędne, dlatego też uwidocznienie tychże skrótów jest bardzo dobrym pomysłem.
• Funkcja KlawiszeMyszy. Jest to możliwość sterowania pozycją kursora myszy przy pomocy klawiszy strzałek z klawiatury numerycznej. Tym, co czyni tę funkcję przydatną, jest precyzja: jedno wciśnięcie przesunie bowiem kursor dokładnie o jeden piksel (w jednym z ośmiu kierunków), co ułatwia pracę z programami graficznymi albo rozmieszczanie elementów interfejsu użytkownika.

Jak wszystkie ułatwienia dostępu, możemy je włączyć przy pomocy odpowiedniego apletu w Panelu sterowania: Centrum ułatwień dostępu w Windows Vista lub Ułatwienia dostępu w starszych wersjach systemu.

PageRank i pozorne rozproszenie Internetu

Znana skądinąd wyszukiwarka Google korzysta z pomysłowego systemu oceniania "wartości" stron zwanego PageRank. W skrócie polega on na obliczeniu średniej ważonej z liczby linków prowadzących do danego dokumentu w sieci WWW. Wagą każdego łącza jest z kolei wartość PageRank jego strony źródłowej. Wynika stąd, że linki pochodzące od "bardziej wartościowych" stron są też skuteczniejsze w podbijaniu rangi stronom, do których wskazują. Naturalnie Google nie publikuje szczegółów algorytmu, ale wiadomo na przykład, że są w nim wykorzystywane... wartości własne pewnej macierzy :)

To, dlaczego PageRank zwrócił moją uwagę, to jego wartość dla tej strony w porównaniu z innymi. Otóż choćby dla takiego Warsztatu ocena jest zaledwie o jeden większa, co wydaje się bardzo dziwne, jako że różnica w dziennej odwiedzalności jest mniej więcej dwudziestokrotna (nietrudno się domyślić, na czyją korzyść ;))
Skąd taki efekt? Po prostu w Google skala PageRank jest logarytmiczna, więc przyrost o 1 punkt oznacza tak naprawdę zwiększenie wartości pewną ilość razy, nie zaś dodanie stałej wartości. To w sumie dość logiczne, jeżeli weźmie się pod uwagę fakt, że kilka(naście/set) najpopularniejszych stron w rodzaju portali czy Wikipedia z łatwością przekroczyłoby skale arytmetyczne.
Jednocześnie widać też, że Internet tylko z pozoru jest siecią rozproszoną.Pod względem łącza mają swoje punkty węzłowe - są nimi wielkie routery przekierowujące gigabity sieciowego ruchu z całych państw i kontynentów. Natomiast jeśli chodzi o sieć spiętą hiperłączami, także mamy pewne kluczowe punkty - czyli witryny oznaczone wysokim współczynnikiem PageRank.