Algorithms Don’t End Here

There is a particular way many programmers tend to think about “algorithms”. I put the word in quotes because it’s a really just a small subset of actual algorithms that they refer to by this term.

In short, “algorithms” are perceived as self-contained boxes, classic procedures that take data in and spit results out. They are blocks, or packages, stowed in a corner of some bigger program, coming out only to perform they designated function. Clearly separated from the “usual” code, they may even occur only as libraries, both standard language libraries or third party extensions.
What’s important is being out of sight, out of mind. You are not supposed to delve into them. You can use them, or add new ones – sometimes even implementing them yourself! – but once you’re done, you get back to “real” code. Normal code, typical code, usual code; code that doesn’t have those “algorithms”.

Amusing as it is, this mode of thinking may actually be spurred by reading works such as the classic Introduction to Algorithms by Cormen et al. Since the subject is intrinsically quite heavy and full of intricate theory and math, it’s very tempting to skirt its surface. Sure, you need to know about most of the important algorithms, but you don’t really have to know them. It’s perfectly acceptable to skip the details of their implementation.
And why not? You can always go back and look it all up! Most of the important stuff is already implemented anyway. When was the last time you had to roll out your own sort() function?… Great programmers reuse, haven’t you heard? We should all stand on the shoulders of giants!

Well, that’s lovely. But I’ve got some bad news. There are no “algorithms”. You cannot compartmentalize programs to have demarcated “difficult” parts. You can try, of course, but it’s futile. They won’t comply, because the pesky reality itself will inevitably tear down any walls you choose to surround the “algorithms” with.

Let’s say you have your isolated, tricky procedure. Over the lifetime of a program that contains it, any of the following is very likely to happen:

• The input data becomes too large to be stored completely in memory. At least some operations will need to be performed at a smaller portion, and then results will have to be merged.
• Waiting for complete input becomes unfeasible. You are now required to compute the result incrementally (or online, to use the traditional term), adjusting it every time a new chunk of information comes in.
• While computational complexity of the algorithm is still acceptable, practical factors mandate limiting of e.g. disk reads or network requests. The procedure needs to be reworked to incorporate additional caching, or pre-computation, or preliminary analysis of input, or obtaining more data outside of main logic, or…
• User studies indicate a growing level of discontent about the lack of UI feedback when performing the Complex and Time-consuming Task™. To alleviate this, the code must now report at least approximate completion progress, so that the interface can be made more responsive by adding a certain widget.
• In an attempt to improve throughput, the application has switched to using asynchronous I/O. As a result, the algorithm must be split into several callbacks and state has to be somehow passed between them. (Extra credit if the programming language has no support, or poor support, for closures).

Many, many other situations could be added to this list, but the point should nevertheless be clear. It doesn’t matter how tightly you’re going to shut the tricky procedure off the rest of the code, the ongoing evolution of the latter will eventually effect changes on it. After a while, you won’t be dealing with a single algorithm, but a whole subsystem with multiple tendrils touching other parts of your program.

At this point, you can’t pretend it can be confined to a dark, forgotten place anymore. Now it has to be taken into account when dealing with the “normal” code on daily basis.
And it’s nothing to fear of, because it simply is just a normal code.

Eksperyment z losowymi ciągami

Zdarzyło się dzisiaj, że musiałem zaimplementować rozwiązanie wyjątkowo klasycznego problemu. Siląc się matematyczny formalizm, mógłbym go zdefiniować następująco:

• Mamy dany zbiór dowolnych elementów oraz liczbę naturalną .
• Szukamy ciągu k elementów .

Krótko mówiąc, chodzi o trywialną wariację z powtórzeniami. Ambitne to zadanie jest w sumie nawet mniej skomplikowane niż częste ćwiczenie dla początkujących pt. losowanie Lotto, więc po chwili wyprodukowałem coś podobnego do kodu poniżej:

I na tym pewnie historia by się zakończyła, gdybym nie przypomniał sobie, że Python domyślnie potrafi obsługiwać naprawdę duże liczby. (Może nie aż tak duże jak te tutaj, ale jednak dość spore ;]). Obserwacja ta daje się bowiem połączyć z inną: taką, iż ciąg elementów z pewnego zbioru jest równoważny liczbie w systemie o podstawie równej mocy tego zbioru. Taka liczba jest oczywiście bardzo duża w prawie każdym praktycznym przypadku, lecz to nie umniejsza w niczym prawdziwości stwierdzenia. Jest ono zresztą z powodzeniem wykorzystywane w systemach kryptograficznych w rodzaju RSA.

Postanowiłem więc i ja z niego skorzystać. Przynajmniej teoretycznie fakt ten powinien dawać lepsze rezultaty, zamieniając k losowań na tylko jedno – tak jak poniżej:

Doświadczenie z kolei uczyłoby, że bezpośrednie aplikowanie dziwnych matematycznych koncepcji do programowania rzadko miewa dobre skutki ;) Jak więc jest w tym przypadku?…

Kwitnące zbiory

Przedstawię dzisiaj interesującą strukturę danych, będącą pewnego rodzaju uogólnieniem lub modyfikacją kontenerów typu bitset. Nazywa się ona filtrem Blooma (Bloom filter) i stanowi przykład struktury probabilistycznej, czyli działającej… czasami ;) Nie niweluje to aczkolwiek w żaden sposób jej przydatności, o czym zresztą opowiem dalej.

Filtr Blooma to tablica bitowa, w której przechowujemy pewien zbiór. Liczba owych bitów – i to jest pierwsza różnica w stosunku do bitsetu – nie jest równa liczbie wszystkich możliwych elementów zbioru. Wręcz przeciwnie, zwykle jest ona znacznie, znacznie mniejsza.
Drugą różnicą jest reprezentacja elementu, która dla odmiany zajmuje więcej miejsca. Definiuje je określona z góry liczba bitów, rozrzuconych po całej tablicy i ustawionych na 1. Sposób owego rozmieszczenia jest określony przez zestaw funkcji haszujących, przyjmujących element zbioru jako swój argument i zwracających indeks jednej z pozycji w tablicy. Owych funkcji jest zaś tyle, ile bitów reprezentacji.

Poglądowe przedstawienie filtru Blooma

Jak wyglądają operacje na tak zaimplementowanych zbiorze? Sprawdzenie przynależności jest proste, bo sprowadza się do obliczenia wartości wszystkich funkcji haszujących dla danego elementu i upewnieniu się, że na zwróconych przez nie pozycjach tablicy jest zapisana jedynka. Dodawanie, jak można się domyślić, polega na ustawieniu tychże jedynek. A co wobec tego z usuwaniem elementu?
Otóż usuwania… nie ma :) Jest to zamierzony efekt, konsekwencja założeń które czynią filtr Blooma strukturą probabilistyczną. Dopuszcza ona mianowicie fałszywe pozytywy. Są to przypadki, w których filtr odpowiada pozytywnie na pytanie o przynależność elementu, gdy w rzeczywistości element ten do zbioru nie należy. Jest to jednak jedyny rodzaj dopuszczalnych błędów. Wykluczone są w szczególności sytuacje odwrotne: gdy element jest w zbiorze, ale filtr odpowiada coś przeciwnego (byłby to z kolei fałszywy negatyw). Usuwanie – polegające na wyzerowaniu odpowiednich bitów – mogłoby jednak do dopuścić do takiej sytuacji. Wynika to z faktu, że każdy z bitów w tablicy odpowiada za przechowywanie więcej niż jednego elementu.

Przypuszczam, że wobec powyższych cech filtrów Blooma pojawiają się dwa pytania, z których jedno dotyczy częstotliwości pojawiania się fałszywych pozytywów. Zależy to oczywiście od rozmiaru tablicy (m), liczby funkcji haszujących (k), a także liczby elementów będących aktualnie w zbiorze (n). Ogólny wzór jest, jak widać, raczej nieoczywisty ;)
Dlatego pozwolę sobie raczej przejść do drugiego pytania: o zastosowania. Te są całkiem rozliczne – dotyczą chociażby przyspieszania dostępu do dużych kolekcji danych. Jeśli koszt wczytania danych odpowiadających danemu kluczowi jest spory (bo wymaga np. odczytu z dysku lub sieci), wówczas utrzymywanie w pamięci filtru Blooma może znacząco polepszyć efektywność poprzez szybkie odrzucanie zapytań o nieistniejące klucze. Oczywiście filtr będzie czasami się mylił, ale jego użycie i tak pozwoli ograniczyć liczbę drogich odwołań co najmniej o rząd wielkości.

Przykładową implementację filtru Blooma – wykorzystującą do haszowania generator liczb pseudolosowych – można zobaczyć choćby tutaj.

Podstawy autouzupełniania

Część bywalców kanału #warsztat może wiedzieć, że od jakiegoś czasu w wolnych chwilach rozwijam pewien niewielki projekt. Jest to prosty IRC-owy bot, który potrafi wykonywać różne predefiniowane czynności, dostępne za pomocą komend rozpoczynających się od kropki. Wśród nich mamy między innymi wysyłanie zapytań do wyszukiwarki Google, wyświetlanie skrótów artykułów z Wikipedii, przekazywanie wiadomości między użytkownikami i jeszcze kilka innych. W sumie jest ich już około kilkanaście, więc pomyślałem, że dobrym rozwiązaniem byłby wbudowany system pomocy oraz podpowiedzi opartych na “domyślaniu się”, jakie polecenie użytkownik chciał wydać.
Brzmi to może nieco zagadkowo, ale w gruncie rzeczy chodzi o zwykłe autouzupełnianie (autocompletion), do którego jesteśmy przyzwyczajeni w wielu innych miejscach – takich jak środowiska programistyczne czy choćby wyszukiwarki internetowe. Oczywiście tutaj mówimy o nawet miliardy razy mniejszej skali całego rozwiązania, ale ogólna zasada we wszystkich przypadkach jest – jak sądzę – bardzo podobna.

Cały mechanizm opiera się właściwie o jedną strukturę danych zwaną drzewem prefiksowym (prefix tree). Jest to całkiem pomysłowa konstrukcja, w której każde dopuszczalne słowo (zwane tradycyjnie w takich drzewach kluczem) wyznacza pewną ścieżkę od korzenia drzewa. Kolejne krawędzie etykietowane są tu znakami słowa.
Najważniejszą cechą drzewa prefiksowego jest jednak to, że wspomniane ścieżki mogą się nakładać, jeśli początkowe części danych słów się pokrywają. Stąd zresztą bierze się nazwa struktury, gdyż pozwala ona szybko znaleźć ciągi zaczynające się od podanego tekstu – czyli właśnie prefiksu.

Funkcja join()

Będąc w zgodzie z podzielanym przez siebie poglądem o kluczowej a często niedocenianej roli “małych” algorytmów, dzisiaj wezmę pod lupę funkcję do łączenia napisów, znaną większości jako join. Ta przydatna operacja występuje w wielu językach i bibliotekach, a jej brak w pozostałych jest zwykle wyraźnie odczuwalny (tak, Java, o tobie mówię). Dobrze użyty join – zwłaszcza w połączeniu z pewnymi specyficznymi mechanizmami językowi – potrafi zapobiec pisaniu niepotrzebnych pętli, znacząco redukując code bloat.

Ale po kolei. join to operacja polegająca na złączeniu kolekcji napisów w jeden, odpowiednio sklejony łańcuch. Łączenie polega na tym, że w wyniku pomiędzy elementami kolekcji wstawiony jest pewien określony ciąg (“klej”). Najlepiej widać to na przykładzie:

Łatwo zauważyć, że join jest w gruncie rzeczy przeciwieństwem funkcji split, którą nieprzypadkowo kiedyś już opisywałem :)

W czym przejawia się przydatność tej operacji? Przede wszystkim rozwiązuje ona “problem ostatniego przecinka” przy wypisywaniu list. Tradycyjnie obchodzi się go mniej więcej tak:
for (int i = 0; i < (int)strings.length(); ++i) { std::cout << strings[i]; if (i + 1 < (int)strings.length()) std::cout << ", "; }[/cpp] Instrukcja if w tej pętli nie jest oczywiście szczytem elegancji. Gdybyśmy mieli tu funkcję join wszystko byłoby o wiele czytelniejsze:
std::cout << join(", ", strings);[/cpp] Drugą zaletą joina jest jego dobra współpraca z modnymi ostatnio, funkcyjnymi rozszerzeniami wielu języków, pozwalająca w zwięzły sposób przetwarzać kolekcje obiektów. Jeśli na przykład mamy słownik (tudzież mapę/hash), to zamiana go na tekstowy odpowiednik klucz=wartość jest prosta:

Oczywiście jest tak wówczas, gdy na widok słowa kluczowego lambda nie uciekamy z krzykiem ;-)

Na koniec tej krótkiej pogadanki wypadałoby jeszcze zaprezentować przykładową implementację omawianej funkcji. Ponieważ – jak napomknąłem wcześniej – doskwierał mi ostatnio jej brak w Javie, więc kod będzie w tym właśnie języku:

Z dokładnością do szczegółów generycznych kolekcji i operacji na stringach, powyższą implementację powinno się dać łatwo przetłumaczyć także na C++.

Optymalizacja jest trudna

Często powtarzanym bon motem jest twierdzenie, iż przedwczesna optymalizacja (preemptive optimization) jest źródłem wszelkiego zła. Dużo w tym racji i równie dużo przesady. Jednak na pewno faktem jest, że pisanie wydajnych i efektywnych, czyli zoptymalizowanych (“przedwcześnie” lub poniewczasie) programów nie jest prostym zadaniem.
W celu łatwiejszej identyfikacji obszarów, w których można zastosować polepszające wydajność poprawki, możliwe rodzaje optymalizacji zwykle dzieli się na kilka rodzajów. Niektóre z nich są aplikowane przez kompilator i pozostają w dużym stopniu poza kontrolą programisty, który może co najwyżej unikać sytuacji blokujących możliwość ich zastosowania – jeśli w ogóle o nich wie. Pozostałe można pewnie zaklasyfikować na kilka sposobów, a podziałem stosowanym przeze mnie jest następujący:

• Optymalizacje projektowe, odnoszące się do wewnętrznej struktury całego projektu i polegające na bardziej efektywnym zorganizowaniu jego modułów, funkcji i klas. Chociaż nie jest to regułą, często oznacza to oddalenie się od uczenie nazywanej “dziedziny problemu” i przybliżenie się do szczegółów technicznych konkretnej platformy.
• Optymalizacje zbliżone do refaktoringu kodu, niezmieniające drastycznie jego architektury, ale modyfikujące kluczowe aspekty implementacji wpływające na wydajność. Prawie zawsze są one związane ze specyficznymi cechami używanego języka lub środowiska.
• Optymalizacje algorytmów, czyli modyfikacje ogólnych przepisów pod kątem konkretnych danych lub zastosowań albo całkowite wymiany jednych algorytmów na inne. Jak nietrudno się domyślić, takie zmiany są raczej niezależne od szczegółów technicznych implementacji, przynajmniej teoretycznie ;)
• Optymalizacje instrukcji, znane też jako mikrooptymalizacje, to po prostu inny sposób wykonywania elementarnych operacji. Być może najbardziej znanym rodzajem takiej poprawki jest używanie przesunięcia bitowego do obliczania potęg liczb całkowitych dla podstawy 2.

Kolejność na powyższej liście odpowiada głównie zakresowi, w jaki optymalizacje wpływają na kształt programu i jego kod. Dość powszechna jest aczkolwiek opinia, że zmiany o bardziej dalekosiężnych skutkach dają też wyraźniejsze efekty, co generalnie nie musi być prawdą. Wystarczy przypomnieć sobie znaną zasadę Pareto, która w tym przypadku oznacza, że 10/20% jest wykonywana przez 90/80% czasu, więc nawet drastyczne optymalizacje zastosowane wobec pozostałej jego części dadzą raczej nikły efekt.
Optymalizację dodatkowo komplikuje wiele innych spraw, jak choćby to, że:

• Niskopoziomowe optymalizacje instrukcji są w zasadzie niepraktyczne w wielu współczesnych językach. Im więcej warstw abstrakcji w rodzaju maszyn wirtualnych oddziela kod źródłowy od instrukcji procesora, tym trudniej określić, jak dana modyfikacja rzeczywiście wpłynie na wydajność i czy nie będzie to przypadkiem wpływ negatywny.
• Optymalizacje projektowe niemal z założenia są “przedwczesne” i wymagają rozważenia jeszcze przed napisaniem kodu programu – lub napisaniem go od nowa. Wymagają więc one doświadczenia i umiejętności przewidywania ich skutków – krótko mówiąc, zdolności prawie profetycznych ;)
• Stosowanie algorytmicznych optymalizacji jest z kolei obciążone ryzykiem potknięcia się o praktyczny aspekt teoretycznych miar takich jak złożoność obliczeniowa. Pamiętać trzeba choćby o tym, że notacja dużego O zakłada rozmiar danych rosnący do nieskończoności i nieważność stałych czynników, co w praktyce nie musi być rozsądnymi założeniami. Dodatkowo niespecjalnie pomaga tu fakt, że współczesne aplikacje są raczej asynchroniczne i interaktywne, więc nie zawierają znowu aż tak wiele algorytmów w klasycznym, proceduralnym, synchronicznym rozumieniu.

Po uwzględnieniu tych uwag wychodzi na to, że najbezpieczniejszym rodzajem optymalizacji jest ten, który polega na odpowiednim refaktoringu kodu – zwłaszcza, jeśli jest on uzasadniony przeprowadzonym uprzednio profilowaniem. Może się bowiem okazać, że najbanalniejsza zmiana, jak np. wydzielenie globalnego obiektu tworzonego w często wywoływanej funkcji, daje natychmiastowy i zauważalny efekt. A jest to efektem jedynie tego, iż optymalizacja była po prostu zastosowana we właściwym miejscu.

I na pewno nie była “przedwczesna” ;P

Maksimum, minimum

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.