Megatutorial M.B - Analiza efektywności algorytmów.pdf - WinAPI - mrozek2002

ANALIZA SPRAWNOŚCI

ALGORYTMÓW

Znane są tysiące sposobów zabijania czasu,

ale nikt nie wie, jak go wskrzesić.

Albert Einstein

Komputery w powszechnym mniemaniu uchodzą za uosobienie szybkości. Nierzadko

przecież zdarza się słyszeć, że oto pokonana została kolejna bariera prędkości obliczeń, a

nowo zbudowany superkomputer w sekundę poradzi sobie z zadaniem, z którym cała

ludzkość musiałaby się biedzić przez setki milionów lat. W takich sytuacjach laicy czasem

zadają sobie pytanie, czy istnieją jeszcze dla komputerów jakieś niewykonalne zadania,

których nie rozwiązałyby w mgnieniu oka. Wydawałoby się, że takich wyzwań już nie ma.

Nasz entuzjazm dla osiągnięć techniki musi jednak przygasnąć, jeżeli przydarzy nam się

typowa przecież sytuacja, gdy musimy oczekiwać na uruchomienie programu na swym

osobistym komputerze. Albo na wyszukanie określonych plików na jego dysku twardym.

Albo na ściągnięcie kilkumegabajtowego pliku przez zapchane łącze internetowe. Albo na

wyrenderowanie gotowej sceny w aplikacji do modelowania 3D. Albo…, albo… - przykłady

można mnożyć w nieskończoność. Zatem nasze komputery nie są wcale takie szybkie.

Czy można coś na to poradzić?…

Intuicja podpowiada nam, że tak. Faktycznie - możemy przecież zakupić szybszy dysk

twardy, zafundować sobie lepsze połączenie z Internetem, wymienić procesor na nowszy,

postarać się o lepszą kartę graficzną, i tak dalej. Wszystko to możemy zrobić my -

użytkownicy , podażąjąc trasą niekończącego się wyścigu technologicznego.

A co mogą zrobić twórcy aplikacji, czyli programiści ? Przecież on nich również zależy

szybkość działania ich produktów: nawet najszybszy dysk twardy będzie bowiem

pracował nieefektywnie, jeżeli zainstaluje się na nim mało wydajny system plików;

najlepsza karta graficzna może sobie nie poradzić z rysowaniem świata gry

trójwymiarowej, jeśli będzie zmuszona do jego całościowego przetwarzania dla każdej

wygenerowanej klatki; wreszcie, nawet najnowszy procesor może się ugiąć się pod

ciężarem skomplikowanych operacji na ogromnym zbiorze danych. Dlatego programiści

muszą dbać o odpowiednią optymalizację działania swoich wytworów, a szczególnie

tych ich części, które są najintensywniej wykorzystywane przez użytkowników.

Optymalizacja jest aczkolwiek trudnym zadaniem, które można wykonywać na wielu

płaszczyznach. Możliwe jest optymalizowanie projektu aplikacji, określającego jej

nadrzędną strukturę - jak choćby klasy i ich składowe. Źle zaprojektowany program ma

bowiem wszelkie szanse, by działać jeśli nie całkiem niepoprawanie, to „przynajmniej”

bardzo nieefektywnie.

Drugą stroną optymalizacji jest dobieranie odpowiednio szybkich algorytmów do

realizacji chociaż tych najbardziej newralgicznych zadań. Efektywny algorytm może

bowiem skrócić czas ich wykonywania setki, tysiące, a nawet miliony (!) razy, produkując

jednocześnie identyczne wyniki.

OK, być może w tej chwili nieco przesadzam. Nie ulega jednak wątpliwości, że dla

każdego niemal zadania istnieją algorytmy lepsze i gorsze, działające szybciej i wolniej,

krótsze i dłuższe w zapisie oraz łatwiejsze i trudniejsze w implementacji - a wszystkie

one są tak samo poprawne w sensie generowanych rezultatów.

Dla wygody programistów najważniejsze byłoby zapewne kryterium prostoty, jednak nie

zapominajmy, że aplikacje tworzymy raczej dla użytkowników innych niż my sami.

Smutną prawdą jest fakt, że takich „postronnych” osób niewiele interesują upodobania

autora programu czy nawet jakość produktu z punktu widzenia inżynierii

oprogramowania; dla nich ważniejsze jest bowiem to, co mogą zobaczyć i odczuć

bezpośrednio: wygodny interfejs użytkownika, rozbudowane możliwości czy nareszcie

szybkość działania.

W interesie popularności naszych dzieł leży więc (między innymi) wybór odpowiednio

efektywnych algorytmów, poprzez które aplikacje będą realizowały swoje cele. Jak

jednak ocenić, który algorytm jest szybszy? Czy istnieją ścisłe kryteria wyznaczania

sprawności danego algorytmu?…

Są to bardzo słuszne i ważne pytania, na które postaram się tutaj odpowiedzieć.

Złożoność obliczeniowa

Kiedy mamy na myśli efektywność wykonania jakiegoś zadania, łatwo możemy

posługiwać się miarą czasową. Zrobienie czegoś w 10 minut jest bardziej efektywne niż

zrobienie tego samego w kwadrans, nie mówiąc już o półgodzinnej czy godzinnej pracy.

Czy jednak podobne kryterium może się stosować do algorytmów?

Wyobraźmy sobie, że mamy do wyboru dwa algorytmy realizujące ten sam cel i

produkujące identyczne wyniki, ale napisane przez dwie różne osoby. Jedna z tych osób

twierdzi, że jej algorytm jest szybki, bo wykonał się w 41 sekund; druga utrzymuje, że

jej algorytmowi zajęło to tylko 29 sekund. Czy znaczy to bynajmniej, że ten drugi sposób

jest szybszy?…

Otóż niezupełnie, bowiem niemal na pewno obie osoby uruchamiały swoje algorytmy w

różnych warunkach . Aby więc obiektywnie porównywać ich sprawność, należałoby te

warunki znać - tzn. wiedzieć:

¾ Jakie komputery zostały użyte w przeprowadzonych próbach?

¾ Jakie procesory posiadały?

¾ Pod kontrolą jakich systemów operacyjnych pracowały?

¾ Czy napisane programy działały w trybie wyłączności, a jeśli nie, to jaki miały

priorytet?

¾ W jakich językach zostały napisane oba programy?

¾ Jakich kompilatorów użyto do ich skompilowania?

¾ Czy w owych kompilatorach były włączone opcje optymalizacji?

¾ itp. itd.

Jak widać, potrzebnych informacji jest całe mnóstwo, zaś nawet posiadanie ich

wszystkich nie upewnia nas, że czegoś nie przeoczyliśmy. Poza tym mając tak szeroki

zasób wiadomości, porównywanie sprawności obu algorytmów wcale nie staje się

prostsze, a w praktyce jest prawie niemożliwe .

Do całego problemu trzeba zatem podejść zupełnie inaczej. Przede wszystkim należy

uświadomić sobie, że algorytm to nie jest skompilowany i funkcjonujący program (lub

jego część), lecz pewien przepis, ogólny ciąg kroków. Co najważniejsze, jest on

niezależny od wszystkich warunków „technicznych”, wymienionych powyżej - nawet od

kompilatora i języka programowania. Ten sam algorytm może być przecież zapisany w

każdym niemal języku; popatrzmy chociażby na kod poszukujący danego elementu

tablicy jednowymiarowej, zapisany w czterech językach programowania:

// C(++)

int Szukaj( const int * pTablica, unsigned uRozmiar, int nSzukany)

{

for ( int i = 0 ; i < uRozmiar; ++i)

if (pTablica[i] == nSzukany)

return i;

return - 1 ;

}

// Object Pascal (Delphi)

function Szukaj( const ATablica : array of Integer; ASzukany : Integer)

: Integer;

var

i : Integer;

begin

for i := 0 to Length(ATablica) - 1 do

begin

if ATablica[i] = ASzukany then

begin

Result := i;

Exit;

end ;

Result := -1;

end ;

' Visual Basic

Function Szukaj(Tablica() As Integer , Szukany As Integer ) As Integer

Dim i As Integer

For i = 0 To Len(Tablica) - 1

If Tablica(i) = Szukany Then

Szukaj = i

Exit Function

End If

Next i

Szukaj = -1

End Function

// PHP

function Szukaj($aTablica, $nSzukany)

{

foreach ($aTablica as $idxIndeks => $nWartosc)

if ($nWartosc === $nSzukany)

return $idxIndeks;

return -1 ;

}

Możliwe jest nawet więcej: algorytm można przecież zapisać, nie używając do tego

żadnego języka programowania , lecz posługując się tylko pseudokodem:

Funkcja Szukaj(Tablica[] : int , Szukany : int ) : int

i: int

Dla Każdego i := Indeks (Tablica) Wykonaj

Jeżeli Tablica[i] = Szukany To

Zwróć i

Koniec

Zwróć - 1

Koniec

W takim wypadku wszelkie rzeczywiste miary, dotyczące faktycznego czasu wykonywania

algorytmu tracą jakikolwiek sens. Potrzebujemy zatem takiego oszacowania, które

pozwoli wyznaczyć efektywność algorytmu nie tylko bez jego kompilacji i uruchamiania,

ale nawet bez zapisywania go w żadnym istniejącym języku programowania. Miara

efektywności powinna bowiem dotyczyć tylko abstrakcyjnego ciągu kroków , jakim jest

każdy algorytm.

Dla zapewnienia ścisłości i wygody czytelników, a także swojej własnej, wszystkie użyte

dalej algorytmy będę jednak zapisywał w języku C++.

Klasa algorytmu

Zdecydowaliśmy więc, że nie będziemy się zajmować rzeczywistym czasem działania

algorytmu na jakimś komputerze, lecz ilością elementarnych kroków , jakie musi on

wykonać, aby wywiązać się ze zleconego mu zadania. Za elementarny krok uważamy

natomiast pojedynczą, prostą instrukcję; przyjęło się zresztą, iż w analizie sprawności

algorytmów bierze się pod uwagę głównie instrukcje porównania , ewentualnie

przypisania.

Teraz trzeba sobie zadać pytanie: czy ilość owych elementarnych kroków będzie w

każdym przypadku taka sama? Nietrudno domyślić się, że nie. Algorytmy tworzymy

przecież po to, aby operowały one na nieznanych z góry danych, zatem pracochłonność

wykonania czynności algorytmu może ściśle zależ eć od tych danych. Dokładniej - może

ona zależeć od rozmiaru wejściowych parametrów algorytmu.

Pojęcie rozmiaru jest tu użyte bardzo ogólnie, a jego dokładne znaczenie jest

nierozerwalnie związane z konkretnym zagadnieniem, czyli rozważanym algorytmem. Dla

przykładowej procedury przeszukiwania tablicy rozmiarem danych będzie oczywiście ilość

elementów tej tablicy; przy sprawdzaniu, czy podana liczba jest pierwsza, decydującą

rolę odegra ona sama; podczas znajdowania pozycji jednego napisu wewnątrz innego

rozmiar danych jest wypadkową długości zarówno przedmiotu, jak i zakresu poszukiwań;

i tak dalej. Można więc stwierdzić, że:

W analizie efektywności algorytmów rozmiar danych jest tą wielkością opisującą

wejściowe dane dla algorytmu, która najbardziej wpływa na ilość kroków podjętych

przy rozwiązywaniu problemu.

Czas wykonywania algorytmu, liczony liczbą elementarnych kroków, najczęściej nie

będzie więc wielkością stałą, lecz funkcją rozmiaru danych wejściowych - funkcją w

rozumieniu matematycznym. Szacowanie efektywności algorytmu polega zatem na

znalezieniu owej funkcji i tym się właśnie teraz zajmiemy.

Znajdujemy złożoność praktyczną

Jako przykład weźmiemy sobie stosunkowo prosty algorytm sortowania, znany jako

sortowanie przez wstawianie (ang. insertion sort ). Być może znasz sposób jego

działania - a jeśli tak, to zapewne wiesz również, że charaktertyzuje się on nieszczególną

efektywnością. Skądkolwiek czerpiesz tą wiedzę, możesz ją teraz zweryfikować.

Przykład: sortowanie przez wstawianie

Najpierw powiedzmy sobie coś o samym algorytmie. Sortowanie przez wstawianie jest

prostym sposobem na uporządkowanie tablicy dowolnych elementów. Oczywistym

warunkiem jest istnienie jakiegoś kryterium możliwego uporządkowania (tzw. porządku

liniowego) wśród elementów tablicy. W praktycznej sytuacji mogą to być złożone zasady

- szczególnie jeśli sortujemy np. rekordy w bazie danych - ale dla nas nie ma to żadnego

znaczenia. Liczy się sama możliwość ustalenia, który element jest mniejszy, a który

większy; dlatego też celem pominięcia takich „technicznych” szczegółów będziemy

zajmowali się wyłącznie sortowaniem liczb całkowitych typu int . Przy użyciu własnych

typów danych i przeciążania operatorów można zresztą w niemal automatyczny sposób

uzyskać algorytm dla dowolnego rodzaju elementów.

Spójrzmy więc na ową procedurę, sortującą tablicę o podanym rozmiarze:

void InsertionSort( const int * aTablica, unsigned uRozmiar)

{

unsigned i, j;

int nElement;

//pętla zewnętrzna, wybierająca po kolei każdy element

//(począwszy od drugiego, czyli tego o indeksie 1)

for (i = 1 ; i < uRozmiar; ++i)

{

nElement = aTablica[i];

//pętla wewnętrzna ma za zadanie stworzyć miejsce dla

// naszego elementu

for (j = i - 1 ;

i >= 0 && aTablica[j] > nElement; --j)

// czyni to, przesuwając elementy do przodu

aTablica[j + 1 ] = aTablica[j];

// a gdy ono już jest, trzeba zapisać element na tym miejscu

aTablica[j+ 1 ] = nElement;

}

Zasada jej działania jest prosta. Zewnętrzna pętla for przebiega po wszystkich

elementach tablicy, natomiast wewnętrzna zajmuje się szukaniem (albo raczej

tworzeniem) właściwego miejsca dla aktualnego elementu. Robi to, przesuwając w stronę

końca tablicy wszystkie liczby, które są większe od tej rozważanej (czyli nElement ). Na

powstały w ten sposób wakat wstawiana jest rzeczona liczba, a wówczas zewnętrzna

pętla zajmuje się kolejnym elementem. Ten jest znowu porównywany z poprzedzaj ącymi

go liczbami, wstawiany na odpowiednie miejsce… i tak dalej, aż do końca tablicy.

Ustalamy reguły

Spróbujmy teraz zająć się sednem sprawy, czyli przybliżeniem czasu działania algorytmu.

Jak wspominałem na początku, interesować nas będzie czas wyrażony w postaci liczby

elementarnych kroków wykonanych przez procedurę.

Co można rozumieć przez to pojęcie? Na zwyczajnym komputerze, dokonującym naraz co

najwyżej jednej czynności, za elementarny krok wygodnie jest przyjmować pojedynczą

instrukcję - zwykle wiersz kodu. Trzeba jednak uważać (zwłaszcza w językach wysokiego

poziomu), by nie robić tego bezmyślnie. Wywołania funkcji nie można bowiem traktować

jako jeden krok, bo jej wykonanie zajmuje w rzeczywistości więcej pracy.

Najrozsądniej jest zatem uważać za pojedyncze kroki najprostsze instrukcje. Należą do

nich głównie przypisania oraz porównania . Dla uproszczenia można jednocześnie

Megatutorial M.B - Analiza efektywności algorytmów.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: