Sortowanie w czasie liniowym

Home

Teoria mówi, że optymalna złożoność obliczeniowa dla algorytmów sortowania opartych o porównywanie wynosi O(nlogn), czyli, innymi słowy, szybciej być już nie może. Taką złożoność optymistyczną ma na przykład używany w .NET algorytm sortowania szybkiego. Ale chwila, co to znaczy sortowanie oparte o porównywanie? To w ogóle istnieje inna możliwość? Przecież, aby posortować na przykład listę liczb całkowitych, to trzeba je porównywać!

Okazuje się, że do problemu można podejść inaczej. Jeśli zrezygnujemy z porównywania, to, pod pewnymi warunkami, osiągniemy złożoność liniową O(n). Niby szybciej, ale czy rzeczywiście warto się tym przejmować? Postanowiłem to sprawdzić i porównałem zachowanie algorytmu sortowania używanego przez .NET, naiwnej rekurencyjnej implementacji sortowania szybkiego oraz algorytmu sortowania w czasie liniowym o nazwie sortowanie przez zliczanie.

Sortowanie przez zliczanie zostało opisane choćby na Wikipedii, dlatego tutaj przybliżę tylko jego ideę. Zacznijmy od tego, że algorytm ten bardzo dobrze nadaje się do sortowania liczb całkowitych z zadanego zakresu, powiedzmy od K do N. Im N mniejsze tym lepiej i jest to oczywiście istotne jego ograniczenie. Jego działanie opiera się na policzeniu, ile razy w tablicy do posortowania pojawiła się liczba K, ile razy liczba K + 1 ... i ile razy liczba N. W tym celu wystarczy odwiedzić każdy element tablicy tylko raz. Kiedy mamy już te informacje, sortowanie właściwie jest zakończone. Na przykład: jeśli liczba 0 wystąpiła 10 razy, a liczba 3 wystąpiła 2 itd., to jako wynik wypiszemy najpierw 10 razy 0, potem 2 razy 3 itd.

Wyniki porównania wspomnianych 3 algorytmów zaprezentowałem na 2 wykresach poniżej. Oś X pokazuje liczbę elementów do posortowania, a oś Y czas sortowania w ms. Pierwszy wykres pokazuje przypadek, kiedy dane do posortowania zawierały liczby z zakresu od 0 do 100, a drugi od 0 do 100 tysięcy.



Wnioski są następujące, niektóre bardzo ciekawe:

• Dla małego zakresu liczb naiwna implementacja sortowania szybkiego działa bardzo słabo (mamy tutaj pesymistyczny przypadek i złożoność O(n^2)).
• Nie widać tego na wykresie, lecz dla małego zakresu liczb sortowanie przez zliczanie jest nieznacznie szybsze od implementacji używanej przez .NET: dla 1 miliona elementów jest to 15 ms w porównaniu do 64 ms.
• W związku z tym pojawia się pytanie, czym różni się naiwna rekurencyjna implementacja sortowania szybkiego od tej używanej przez .NET? Można by o tym dużo napisać, więc tutaj tylko zasygnalizuję o co chodzi. Otóż w rzeczywistości .NET używa tzw. sortowanie introspektywnego, który stanowi połączenie "zwykłego" sortowania szybkiego, sortowania przez kopcowanie i sortowania przez wstawianie, przez co wyeliminowano przypadek pesymistyczny, kiedy QuickSort ma złożoność wielomianową.
• Dla dużego zakresu elementów różnica pomiędzy 3 porównywanymi algorytmami zaciera się chociaż rekurencyjna implementacja QuickSort jest wciąż najwolniejsza, a sortowanie przez zliczanie jest trochę szybsze od tego co oferuje .NET.
• Sprawdziłem czas sortowania dla maksymalnie 50 milionów elementów i trwało to 2 s dla sortowanie przez zliczanie oraz 5 s dla hybrydowego.
• Wniosek końcowy jest taki, że biorąc pod uwagę ograniczenia i wady sortowania przez zliczanie oraz to, jak dobrze działa implementacja hybrydowa w .NET należy jej po prostu używać i nie zastanawiać się specjalnie nad innymi wynalazkami.

Desktop Heap

Home

W swojej pracy bardzo lubię dowiadywać się o zupełnie nowych rzeczach, o których jeszcze nigdy nie słyszałem. Ostatnio taką nowością dla mnie było pojęcie desktop heap (sterta pulpitu???). Jest to coś, czym 99% z nas przez 99% czasu nie ma potrzeby się zajmować, a zainteresujemy się tym dopiero, jak to często bywa, kiedy pojawią się kłopoty.

Ja spotkałem się z desktop heap przy okazji problemów z usługami systemowymi tj. jeszcze kilka minut temu nie było kłopotów i nagle przestały się uruchamiać. W logu systemowym pojawił się natomiast komunikat podobny do poniższego:

Could not find file ‘C:\WINDOWS\TEMP\ayui23kj.dll’

Kolega znalazł artykuł, który jako winowajcę wskazywał właśnie desktop heap i było to strzałem w dziesiątkę. Pojęcie to zostało dobrze opisane w tym artykule, dlatego tutaj opiszę je tylko pokrótce. Zacznijmy od tego, że w systemie Windows mamy pojęcie sesji (ang. session) pod którym kryje się ogół zasobów powiązanych z pojedynczym zalogowanym użytkownikiem.

W ramach sesji może istnieć wiele window station. Obsługują one schowek i zawierają w sobie różne procesy oraz pulpity (ang. desktop). Warto zapamiętać, że tylko jedna stacja może komunikować się z użytkownikiem i nazywa się ona Winsta0.  Co okaże się ważne później, wszystkie usługi systemowe działające na tym samym koncie zostają przydzielone do tej samej stacji.

To dość daleka analogia, ale stacja przypomina mi domeny aplikacyjne znane z platformy .NET. Domeny aplikacyjne to takie małe procesy, które służą zwiększeniu bezpieczeństwa przez separację różnych zadań od siebie, a więc oba pojęcia mają podobną rolę.

Wspomniane pulpity zawierają w sobie wirtualną/logiczną przestrzeń, na której można coś wyświetlić. To również pojemniki na obiekty interfejsu użytkownika takie, jak okna i menu. Dokładniej obiekty te przechowywane są w części pulpitu zwanej właśnie stertą. Problem polega na tym, że sterta ma ograniczoną wielkość i może się zapełnić, i tak było w moim przypadku.

Wielkością sterty można co prawda sterować (patrz tutaj oraz tutaj), ale pytanie brzmi co spowodowało jej przepełnienie. W moim przypadku problemem okazała się zła obsługa niezarządzanych zasobów przez jedną z usług. Zasoby te nie były poprawnie zwalniane i wypełniały stertę, dodatkowo blokując inne usługi. Po wprowadzeniu poprawki problem z uruchomieniem usług ustąpił.

Na koniec chcę zwrócić uwagę na jedną rzecz. Ta jedna usługa blokowała inne bo wszystkie działały na tym samym koncie. W związku z tym korzystały z tej samej stacji, pulpitu i sterty. To co potwierdziło przepełnienie sterty był fakt, że zmiana konta używanego przez usługę powodowała, że można ją było poprawnie uruchomić. Innymi słowy zmiana konta powodowała przeskoczenie do innej stacji, a więc również do innej, nie wypełnionej sterty.

Czy użycie if zamiast else if ma znaczenie?

Home

Historia zaczyna się od prostego fragmentu kodu pokazanego poniżej. Kod ten to fragment walidatora, ktory ma za zadanie określić, czy dane są prawidłowe. Jeśli nie, to zmienna isValid powinna zostać ustawiona na false.

var isValid = true;

if (condition_1)
   isValid = false;

if (condition_2)
   isValid = false;

Kod ten działał do momentu, kiedy wprowadzono do niego małą zmianę pokazaną poniżej. Było to pewne uszczegółowienie logiki walidacji danych wejściowych.

var isValid= true;

if (condition_1)
   isValid = false;

if (condition_2)
   isValid = false;
//Wprowadzona zmiana
else 
{
   if (condition_3)
      isValid = true;
   else if (condition_4)
      isValid = false;
}

Po zastanowieniu się z pewnością stwierdzicie, że coś tutaj nie pasuje. Problem polega na tym, że w określonych warunkach zmienna isValid może zostać z powrotem ustawiona na true nawet jeśli wcześniej stwierdzono, że dane są błędne i ustawiono ją na false!

Może są jakieś rzadkie i dziwne przypadki kiedy błędne dane mogą stać się nagle poprawne, ale w przypadku, z jakim się spotkałem, był to ewidentny błąd i przeoczenie albo brak zrozumienia działania kodu. Moim zdaniem błąd tkwi jednak w jeszcze jednym miejscu tj. w użyciu wielu if'ów zamiast konstrukcji else if w kodzie pokazanym na samym początku. Gdyby początkowy kod wyglądał w ten sposób:

var isValid = true;

if (condition_1)
   isValid = false;
// else if zamiast if
else if (condition_2)
   isValid = false;

To nawet jego modyfikacja w opisany wcześniej sposób nie spowodowałaby, że walidator pozwolił na kontynuację przetwarzania pomimo błędnych danych. Może wydawać się, że kilka if'ów zamiast użycia else if nie robi różnicy bo to przecież oczywiste jak ten kod działa. Może i oczywiste, ale tu i teraz. Za kilka tygodni lub miesięcy, dla kogoś innego, może już nie być takie oczywiste. Ktoś inny może również to po prostu przeoczyć.

Tworząc kod trzeba się starać, aby był możliwie łatwy do zrozumienia, rozszerzania i wprowadzania zmian, a w tym celu w przypadkach podobnych do opisanego wystarczy po prostu użycie trochę inne konstrukcji językowej, która lepiej wyrazi nasze zamiary innym.

LaTeX + PDF + obrazki

Home

Korzystając z LaTeX'a dokumenty PDF można tworzyć na przynajmniej dwa sposoby. Te znane mi to:

• Pliki źródłowe *.tex -> dokument w formacie DVI -> PDF
• Pliki źródłowe *.tex -> PDF

W pierwszym przypadku używamy dwóch programów tj. latex.exe oraz dvipdfm.exe, a w drugim tylko jednego tj. pdflatex.exe. Do tej pory stosowałem pierwsze podejście, ale w pewnym momencie chciałem skorzystać z szablonu, który był dostosowany do drugiego podejścia. I tu zaczęły się problemy, na których straciłem dużo czasu, a więc piszę ten post ku pamięci. Problemy te dotyczyły osadzania obrazków w dokumencie PDF.

Pierwszy problem polegał na tym, że kompilator krzyczał, że nie rozpoznaje rozszerzenia PS. To udało mi się przewalczyć w miarę szybko zmieniając rozszerzenia na EPS. Dziwne, ale zadziałało. Jakie było jednak moje zdziwienie kiedy po otworzeniu wygenerowanego dokumentu PDF nie znalazłem w nim żadnych obrazków, a dokładniej w miejscach przeznaczonych na obrazki widniały białe obszary o rozmiarze obrazków! Rozwiązanie okazało się jest dziwniejsze niż wcześniej. Otóż, wystarczyło z nazwy obrazka usunąć rozszerzenie czyli zamiast obrazek.eps wpisać obrazek.

Na tym nie koniec. Po jakimś czasie udało mi się doprowadzić do sytuacji kiedy obrazki były widoczne w dokumencie PDF zarówno kiedy nazwa zawierała rozszerzenie jak i bez niego. Otóż w celu umieszczenia w dokumencie obrazka w formacie JPG najpierw konwertuję go do formatu PS przy pomocy programu jpeg2ps.exe. Nie pamiętam już dlaczego, ale jpeg2ps.exe używałem z przełącznikiem -b. Nie wnikając w szczegóły do czego służy, po jego usunięciu problem ustąpił.

Mam nadzieję, że te krótkie wskazówki oszczędzą komuś czasu. Cały czas uważam, że LaTeX jest wspaniałym narzędziem, ale czasami potrafi doprowadzić do szewskiej pasji.

Konferencja wewnątrz-firmowa - edycja 2

Home

Rok temu tutaj oraz tutaj opisałem zorganizowaną przez siebie konferencję wewnątrz-firmową. W tym roku odbyła się jej druga edycja. O szczegółach organizacyjnych nie będę pisał, aby się nie powtarzać. Z drobnymi szczegółami wyglądało to podobnie. Tematy prezentacji były przynajmniej tak ciekawe, jak przed rokiem i można było posłuchać następujących wystąpień:

Janusz Prusaczyk - Introduction to PowerShell scripting

Paweł Kupis - C# 5.0 Async Feature (async/await) and Synchronization Context – the old new friends

Marcin Wierzbicki - Praktyczny pomiar i atrybucja efektywności portfela inwestycji finansowych

Kamil Langowski - Wolfram Alpha: Computational Knowledge Engine

Adam Juszkiewicz - Mobile game development in Unity

Albert Skłodowski - Design Patterns in Functional Programming

Daniel Celeda - Kręgosłup programisty

Jaroslaw Trafidlo - Czy możemy czuć się bezpiecznie podłączając komputer do sieci?

Damian Orzechowski - Silniki gier komputerowych

Paweł Kaczan - Claims based itentity

Mikołaj Barwicki - Science of Motivation

Michał Komorowski - Debuggery historyczne, co to takiego?

Konferencja ponownie udała się i nie jest to tylko moja opinia. Znowu można było posłuchać o najróżniejszych rzeczach, typowo technicznych, wymagających więcej i mniej uwagi, luźnych... i właśnie to mi się w tym wszystkim najbardziej podoba. Być może się powtórzę, ale pozwala to dowiedzieć się o rzeczach, którymi na co dzień zupełnie się nie interesujemy i nawet do głowy nam nie przyjdzie, że jednak warto. Zdecydowanie polecam.

Mam też trochę wniosków na przyszłość. Było bardzo fajnie, ale zawsze może być lepiej. Jednym z pomysłów na poprawę jest wprowadzenie szablonu prezentacji z przykładami oraz ostrego limitu na poziom slajdów. Szablon powinien zapewnić, że wszystkie prezentacje będą równie czytelne oraz, że nikogo nie porwie zbytnia fantazja przy tworzeniu slajdów ;) Limit na liczbę slajdów powinien natomiast ułatwić zmieszczenie się w czasie. Po głowie chodzi mi również zaproszenie na konferencję ludzi z poza firmy. Może to być trudne do zrealizowania, ale może się uda. Co o tym myślicie, bylibyście chętni do wzięcia udziału w takim wydarzeniu?

Z nowości względem poprzedniej edycji, w tym roku wystąpienia były nagrywane. A wszystko dzięki uprzejmości Jarka Trafidło, który udostępnił kamerkę z serii GoPro, był operatorem, a także poddał zgromadzony materiał obróbce. Jeśli ktoś nie był na jakiejś prezentacji, to będzie mógł ją teraz obejrzeć na spokojnie w domu.

Z mojej perspektywy ogromnym dodatkowym plusem tych nagrań jest to, że w końcu mogłem sporzeć na siebie od tej drugiej strony. Przyznam, że to trochę dziwne uczucie, bo głos brzmi jakoś tak inaczej i w ogóle percepcja siebie się zmienia. Na przykład, wiedziałem, że dużo gestykuluję, ale nagranie pokazało, że chyba zbyt dużo. Po drugie, występując wydawało mi się, że ogólnie stoję w miejscu i tylko od czasu do czasu zrobię krok w jedną albo w drugą stronę. Nagranie znowu uświadomiło mi, że poruszam się więcej niż mi się wydaje, a to kroczek w tą, a to kroczek w drugą. Nie mówię, że trzeba stać w miejscu, ale zbytnia ruchliowść również przeszkadza. Bardzo cenne wskazówki na przyszłość.