Zasada gołębiej dziury

Dzisiejsza notka będzie o pewnej matematycznej ciekawostce, która pokazuje, że nawet pozornie oczywiste stwierdzenie mogą mieć daleko idące konsekwencje, jakich nie da się na pierwszy rzut oka przewidzieć. Mamy mianowicie pewną kombinatoryczną regułę, mówiącą (w jednej z wersji), że:

Jeżeli n obiektów umieścimy w m < n pudełkach, to znajdzie się pudełko zawierające więcej niż jeden obiekt.

Zaskakujące, prawda? ;-) Wydaje się, że niewiele jest rzeczy bardziej oczywistych. A jednak powyższe twierdzenie doczekało się swojej własnej nazwy - i to nawet takiej, która uwzględnia nazwisko odkrywcy! W języku polskim mówimy mianowicie o zasadzie szufladkowej Dirichleta, a analogią jest podobno układanie skarpetek w szufladach. W angielskim z kolei używa się do tego... gołębi, a reguła jest znana jako pigeonhole principle - w dosłownym tłumaczeniu 'zasada gołębiej dziury'.

Co jest niezwykłego w tak prostej obserwacji? Otóż jej wyjątkową cechą jest to, że stosuje się do wręcz nieograniczonego spektrum zjawisk różnego typu i wielu dziedzin, pozwalając udowadniać prawdziwość mnóstwa czasami zaskakujących stwierdzeń. Ich ciężar gatunkowy może się wahać od zabawnych, aczkolwiek pouczających, aż do zupełnie kluczowych dla niektórych dziedzin nauki. Oto przykłady:

• Struktury danych oparte na haszowaniu zawsze muszą uwzględniać metody rozwiązywania kolizji. Ten znany fakt jest konsekwencją tego, iż liczba możliwych kluczy n przekracza (zazwyczaj znacznie) rozmiar pojemnika m, więc nawet przy najlepszej funkcji haszującej znajdą się takie dwa klucze, które zostaną przyporządkowane w to samo miejsce.
• W pudełku jest 5 czarnych i 5 białych kul. Ile co najmniej kul musimy wybrać, żeby wśród nich znalazła się para tego samego koloru? Nie, wcale nie sześć - wystarczą trzy. Skoro mamy m = 2 kolorów, to już n = 3 kul gwarantuje, że będzie wśród nich para tego samego koloru.
• Wśród wszystkich obecnie żyjących ludzi co najmniej dwójka wypowiedziała w ciągu swojego dotychczasowego życia identyczną liczbę słów. Nawet gdyby ktoś paplał 24 godziny na dobę z prędkością jednego słowa na sekundę, w ciągu jednej doby nie powie ich więcej niż 86.400. Najstarszy człowiek miał/ma około 130 lat, w związku z czym ilość możliwych wartości dla wielkości 'liczba wypowiedzianych słów' to ok. 86.400 * 365,25 * 130, czyli nieco ponad 4 miliardy. Ponieważ na Ziemi żyje obecnie ponad 6 miliardów ludzi - czyli więcej - na mocy zasady szufladkowej wnioskujemy, że musi istnieć co najmniej dwójka, która wypowiedziała w ciągu życia tę samą liczbę słów.
• Jeśli algorytm kompresji bezstratnej rzeczywiście kompresuje (tj. zmniejsza objętość przynajmniej jednego pliku), to istnieje dla niego taki plik, który po "kompresji" będzie większy niż przed nią. Innymi słowy, nie ma doskonałych metod kompresji i nawet rosyjscy hakerzy nic na to nie poradzą :) Jest to bowiem bezpośrednia konsekwencja zasady 'gołębiej dziury'.
  Powiedzmy, że najmniejszy plik faktycznie kompresowany (tj. zmniejszany) przez nas algorytm ma początkowy rozmiar , zaś po kompresji jest to już , gdzie . Istnieje skończona liczba plików rozmiaru , którą oznaczymy . (Jeśli na przykład jest to rozmiar w bajtach, to ). Z założenia żaden z tych plików nie zmienia rozmiaru podczas kompresji, więc ich wielkość po skompresowaniu to również . Oznacza to jednak, że tych plików to wyniki kompresji plików, bo także (większy niż ) jest kompresowany do jednego z tych plików. Ponieważ , na mocy zasady szufladkowej istnieją dwa takie pliki - mianowicie i jakiś plik rozmiaru - które są kompresowane do tego samego pliku wyjściowego. Jeśli tak jest, to algorytm nie może być bezstratny - czyli mamy sprzeczność, Q.E.D. :-)

Całkiem sprytne, nieprawdaż? Jak na zupełnie "oczywistą oczywistość", zasada szufladkowa wykazuje niezwykłą użyteczność w wielu zaskakujących momentach. Warto o niej pamiętać nie tylko podczas poszukiwań pary pasujących skarpetek :)

C# i zbiory

Dłuższy czas temu popełniłem notkę o tym, że w C# (lub szerzej: w .NET) brakuje pewnych struktur danych, które niekiedy bywają przydatne. Jedną z nich jest bardzo prosty rodzaj pojemnika: zbiór.
Zbiory (w programowaniu) to kontenery, które przechowują elementy niepowtarzające się i umożliwiają szybkie sprawdzenie, czy jakaś wartość do danego zbioru należy. 'Szybkie' oznacza tu złożoność logarytmiczną (względem rozmiaru pojemnika) lub lepszą. Podstawowa różnica w stosunku do zbiorów matematycznych jest natomiast taka, iż te drugie mogą zawierać elementy różnych rodzajów, podczas struktura danych o tej nazwie przechowuje obiekty jednego typu.

W C++ zbiór implementuje STL-owa klasa std::set. W C# z kolei - jak napisałem na początku - jej odpowiednika nie ma. Takowy trzeba by dopiero napisać, co w przypadku tego języka jest raczej zaskakujące :) Tym niemniej da się to zrobić w miarę prosto, używając do tego... klasy Dictionary. Pomysł polega na tym, żeby całkowicie zignorować tę jej część, która kluczom w słowniku pozwala przypisywać wartości. Zamiast tego interesują nas wyłącznie same klucze jako elementy naszego zbioru. Zarys klasy opartej o tę ideę może wyglądać choćby tak:

Skorzystanie ze słownika (klasy Dictionary) sprawia, że kluczowa operacja Contains (sprawdzenie przynależności) jest bardzo szybka. MSDN podaje, że wydajność odpowiadającej jej operacji słownikowej ContainsKey "zbliża się do O(1)". Mamy tu też oczywiście niezbędne metody do dodawania i usuwania elementów, a także kilka innych związanych z implementowanymi interfejsami ICollection i IEnumerable, które pozwalają na przykład na iterowanie po zbiorze pętlą foreach.
Można naturalnie jeszcze ulepszyć tę klasę, dodając nowe konstruktory, metody i implementując następne interfejsy (na przykład ISerializable). Nie jest to trudne, bo polega głównie na wywoływaniu odpowiadających metod obiektu Dictionary lub jego kolekcji kluczy. Dopiero operacje matematyczne - jak suma i iloczyn zbiorów - wymagałoby nieco większej ilości kodu.
Ale przecież dla chcącego nic trudnego :)

Szablony klas i funkcje zaprzyjaźnione

Chcę dzisiaj napisać o pewnego rodzaju "ciekawostce", związanej z dwoma pojęciami z tytułu notki, na którą natknąłem się jakiś czas temu. Po zredukowaniu nadmiaru szczegółów można przyjąć, że rzecz dotyczy sytuacji, w której mamy szablon klasy oraz zadeklarowaną wewnątrz niego funkcję zaprzyjaźnioną - na przykład przeciążony operator strumieniowy <<:

Funkcja jest zadeklarowana, lecz nie jest od razu zaimplementowana wewnątrz bloku class. Zamiast tego umieszczamy jej kod osobno:

co jest może trochę osobliwe, ale wydaje się poprawne. No właśnie; wydaje się. Próba użycia tak zdefiniowana operatora:

nie przeszkadza wprawdzie kompilatorowi, jednak linker ma poważne zastrzeżenia. Okazuje się, że funkcja operator << w wymaganej postaci nie jest zdefiniowana - czyli mamy zwyczajny unresolved external, aczkolwiek o niecodziennych przyczynach.

Przyznać muszę teraz, że nie jestem do końca pewien co do ich natury, jako że konsultacja z zaufanymi źródłami (w postaci książki C++. Szablony panów Vandevoorde'a i Josuttisa) nie dała jednoznacznej odpowiedzi, co tutaj tak naprawdę się dzieje. Przypuszczam, że ma tu miejsce pewien dziwnej interakcji między konkretyzacją szablonu klasy a deklaracją friend, która przy okazji jest też deklaracją funkcji operator <<. Mimo że nie stanowi ona części szablonu, owej konkretyzacji podlega, czego skutkiem jest stworzenie zwykłej (nieszablonowej) deklaracji:

Nie ma więc ona nic wspólnego z szablonem funkcji operator <<, który jest zdefiniowany później! W rzeczywistości wygląda zresztą tak, że ów szablon jest całkowicie pominięty przy kompilacji jako niewykorzystywany; to zapewne z powodu reguł przeciążania funkcji w C++, nakazujących najwyraźniej wybranie raczej funkcji nieszablonowej (o powyższej deklaracji) zamiast szablonu funkcji. A że przypadkiem funkcja ta nie ma implementacji... Cóż, kompilator nie ma obowiązku się o to martwić :)

Tyle moja teoria. Niezależnie od tego, czy jest ona prawdziwa czy nie, dobrze byłoby wiedzieć, jak z problemu wybrnąć. Naturalnym wyjściem jest przenieść kod funkcji tam, gdzie jego miejsce - czyli z deklaracji funkcji w klasie (opatrzonej słówkiem friend) uczynić też jej definicję. Faktycznie, to działa; najwyraźniej powstaje wtedy nieszablonowa funkcja o nagłówku danym wyżej, razem ze swoją implementacją - czyli wszystko jest w porządku.
Drugie rozwiązanie to opatrzenie deklaracji friend klauzulą template:

W tej wersji - jak sądzę - następuje zaprzyjaźnienie każdej specjalizacji klasy Foo z odpowiadającą jej specjalizacją metody operator <<. Oba szablony podlegają niezależnym konkretyzacjom, ale linker potrafi prawidłowo rozwiązać relację między nimi.

Uff, trochę to skomplikowane. Jak widać, z zaprzyjaźnianiem bywają problemy - i to nie tylko dlatego, iż "In C++ friends touch each other's private parts." ;) Dziwne efekty związane z szablonami i konkretyzacją potrafią bowiem skonfudować nawet doświadczonych programistów.

Dwukierunkowe funkcje i obiekty proxy

Jedną z pierwszych rzeczy poznawanych w trakcie nauki programowania jest sposób działania funkcji. Mam tu na myśli zupełnie elementarny fakt, iż funkcje przyjmują zero lub więcej argumentów na wejściu i produkują co najwyżej jeden rezultat na wyjściu. Niezachwiana pewność w tę własność funkcji może być potem mocno nadwątlona, jeśli poznamy języki o bardziej egzotycznym sposobie działania, jak na przykład Prolog; tam wszystkie parametry funkcji mogą przekazywać dane w obu kierunkach, dzięki czemu np. za dzielenie i łączenie ciągów lub list odpowiada jedna i ta sam funkcja.
Nie trzeba jednak uciekać tak daleko od starego dobrego programowania imperatywnego, żeby zaobserwować odstępstwa od reguły. Parametry mogą przecież służyć do zwracania wartości - dzieje się to przy pomocy słów kluczowych ref/out w C# lub zwykłych wskaźników/referencji w C++. Często zdarza się wtedy, że "normalny" rezultat zwracany przez funkcję służy jedynie przekazaniu informacji o ewentualnym błędzie.

Rzadsza sytuacja polega na tym, że wynik funkcji staje się jej argumentem wejściowym. Technicznie nie jest nawet możliwe, ale można tak traktować sytuacje, gdy rezultatem jest l-wartość (l-value), tj. obiekt, do którego można przypisywać:

Typowo jest to referencja (tutaj int&), a powyższa konstrukcja - poprzez swojej podobieństwo do indeksowania zwykłej tablicy - nie należy do wielce zaskakujących. Co jednak można powiedzieć o tej:

poza widocznym od razu faktem, że pochodzi ona z języka, którego rozwlekłość składni przyprawia o niestrawność? :) Mianowicie tutaj nie ma już oczywistych przesłanek co do tego, czym jest lewa strona. Widać bowiem, że możemy jej przypisać dłuższy podciąg niż oryginalny i zostanie on mimo wszystko poprawnie zastąpiony - nie jest to więc żaden prosty "wyrób wskaźnikopodobny". Może więc to po prostu feature akurat tego języka, którego nie da się zreplikować?...

Odpowiedź jest - jak można się domyślać, skoro o tym piszę - oczywiście negatywna :) Ażeby podobny efekt osiągnąć w C++, konieczne jest jednak zastosowanie techniki znanej jako obiekt pośredniczący - proxy. Powinien on zachowywać się jak zwykły rezultat funkcji, ale w razie potrzeby dawać również możliwość przypisywania do siebie. Naturalnie efekt takiego działania jest specyficzny dla konkretnej funkcji, która swoją drogą może być często zredukowana do samego tworzenia obiektu proxy:

Minimum, jakie rzeczony obiekt musi zapewniać, to operator przypisania oraz jakiś operator rzutowania, który pozwoli na "wyciągnięcie" rezultatu funkcji, gdy jest ona użyta w zwykły sposób:

Widzimy tutaj, że przy takim proxy nasza funkcja Mid użyta w zwykły sposób zachowuje się jak metoda substr. Gdy jednak umieścimy jej wywołanie po lewej stronie przypisania, zadziała metoda replace, służąca do zastępowania podciągu innym. W sumie więc poniższy kod:

będzie działał analogicznie do prezentowanego wyżej fragmentu w języku Visual Basic.

Opisana tu sztuczka nie jest oczywiście doskonała. Do pełni możliwości potrzebna jest jeszcze wersja read-only funkcji Mid, przyjmująca stałą referencję do stringa i wywołująca substr bezpośrednio, z pominięciem obiektu proxy. To jednak da się łatwo zauważyć.
Mniej widoczny jest natomiast fakt, że obiekt proxy, dodając kolejną warstwę niejawnych konwersji (tutaj: z siebie na string) może spowodować kłopoty tam, gdzie jedna niestandardowa konwersja jest już wykorzystywana. Dobry przykład to interakcja ze strumieniem:

która nie powiedzie, bo operator strumienowy << nie posiada wersji dla lewego prawego argumentu będącego std::stringiem, a jedynie dla const char* (co swoją drogą jest dość dziwne). Rozwiązaniem jest napisanie takowego dla samego obiektu proxy.