16 maj, 2009
Testowanie złożoności obliczeniowej 2 algorytmów w Pythonie
Zamieszczony przez: Justi w: Python
Postanowiłam sprawdzić w praktyce, jak się mają teoretyczne wyliczenia złożoności obliczeniowej algorytmów do rzeczywistych wyników uzyskiwanych w kompilatorze.
Do testów wybrałam język Python oraz kompilator Eclipse.
Problem:
Znaleźć minimalny i maksymalny element w tablicy n-elementowej.
Można to zrobić na 2 sposoby:
1) przechodząc po kolei po każdym elemencie tablicy zadecydować, czy przypisać go do min lub max. Złożoność tego algorytmu to ok. 2n
2) porównywać ze sobą 2 kolejne elementy i zadecydować który przypisać do min a który do max. Złożoność tego algorytmu to ok. 3*n/2 = 1,5n
Jak wynika ze wstępnych założeń, algorytm drugi powinien być o ok. 25% szybszy niż pierwszy.
Zapis w Pythonie:
Algorytm 1:
def algorytm1(tab):
min = 0
max = 0
t1 = time.clock()
for i in range(0,ilosc,1):
if (tab[i] > max):
max = tab[i]
if (tab[i] < min):
min = tab[i]
t2 = time.clock()
return t2-t1
Algorytm 2:
def algorytm2(tab):
min = 0
max = 0
t1 = time.clock()
for i in range(0,ilosc,2):
if(tab[i] > tab[i+1]):
if (tab[i] > max):
max = tab[i]
if (tab[i+1] < min):
min = tab[i+1]
else:
if (tab[i+1] > max):
max = tab[i+1]
if (tab[i] < min):
min = tab[i]
t2 = time.clock()
return t2-t1
Obie funkcje zwracają różnicę czasu pomiędzy momentem swojego startu i zakończenia.
Tablice testową program tworzy z losowo wybranych liczb typu całkowitego z przedziału od 1 do 1000. Wielkość tablicy przekazywana jest jako parametr tej funkcji.
def genTab(ilo):
tablica = []
for i in range(ilo):
tablica.append(round(random.random() * 1000))
return tablica
Cały program do ściągnięcia:
zlozonosc.py (1,4 KiB, 1 468 hits)
Program zwraca procentową różnicę czasu działania między algorytmem drugim a pierwszym. Jest to średnia z x prób (ostatnia pętla).
Wyniki zaprezentowane są na wykresie:
Jak widać, różnica w szybkości działania obu algorytmów jest tym bardziej widoczna, im większy jest rozmiar danych, (n-> nieskończoności).
Jeszcze wykres średniej procentowej wzrostu:
A gdyby nieco zoptymalizować kod algorytmu numer 2?
Dopisałam w nim 2 linijki kodu
zm1 = tab[i]
zm2 = tab[i+1]
po to, aby nie odwoływać się za każdym razem do samej tablicy (która może być stosunkowo duża), zamiast tego zrobić to raz, na samym początku.
Wyniki są ciekawe:
Dla dużych wartości n szybkość działania algorytmu drugiego względem pierwszego wzrosła z ok 20% do ok. 27,5% 
Program po optymalizacji do ściągnięcia:
zlozonoscZopt.py (1,4 KiB, 1 094 hits)
// implementację drugiego algorytmu a tymczasem pierwszy również można zoptymalizować. Co więcej poprawa drugiego algorytmu tak aby działał również dla parzystej długości danych mogłaby spowodować spadek wydajności (chociaż prawdopodobnie tak się nie stanie).
Najnowsze komentarze