Student: A
ukasz Rychter Warszawa, 20.12.2009
Nr indeksu: 218882
Grupa studencka: 3M2
Data lab. 11.12.2009 16.15-18.15
Prowadzący: dr inż. Grzegorz Janczyk
Laboratorium AISDE
Sprawozdanie z dwiczenia 4:
Analiza właściwości struktur danych algorytmów
zastosowanych do implementacji kolejki priorytetowej
1) Zadanie i cel dwiczenia
Celem dwiczenia było zapoznanie się z różnymi możliwymi implementacjami kolejki priorytetowej, ze względu zarówno na strukturę przechowywania
danych, jak i na algorytm używany do wybierania elementu o najwyższym priorytecie (zazwyczaj występujący w wersji  leniwej jak i  nadgorliwej ).
Zaobserwowad należało wydajnośd i przydatnośd poszczególnych implementacji w zależności od typu elementów danych oraz sekwencji operacji
wstaw/wyjmij.
Do moich zadao należało wykonanie poleceo a) oraz f) z instrukcji do dwiczenia:
a) zbadad dla jakich sekwencji metod put/get podejście leniwe jest lepsze/gorsze/takie samo jak nadgorliwe.
f) zastosowad inne algorytmy w implementacji metod kolejki (np. kolejka nadgorliwa ze wstawianiem danej metodą połowienia, kolejka leniwa z
sortowaniem daną metodą, itp.)
2) Wykonanie poleceo
f) Zastosowad inne algorytmy w implementacji metod kolejki (np. kolejka nadgorliwa ze wstawianiem danej metodą
połowienia, kolejka leniwa z sortowaniem daną metodą, itp.)
Zaimplementowałem 2 dodatkowe algorytmy:
I) Kolejkę nadgorliwą ze wstawianiem z użyciem połowienia
II) Kolejkę leniwą z sortowaniem algorytmem QuickSort
I) Implementację kolejki z połowieniem przy wstawianiu stworzyłem wykorzystując szkielet klas i funkcji , na których bazowały inne algorytmy w zadanym
programie testowym oraz używając funkcji BisekcjaDoWstawiania zaczerpniętej z kodu z
ródłowego do laboratorium 2 AISDE.
// Kolejka priorytetowa nadgorliwa dzialajaca z użyciem bisekcji przy wstawianiu
#ifndef BISECTION_QUEUE_H
#define BISECTION_QUEUE_H
#include "SmartBubble.h"
#include "AbstractPriorityQueue.h"
template
class BisectionQueueOfficious : public AbstractPriorityOfficiousQueue, public SmartDataTable
{
public:
BisectionQueueOfficious() : AbstractPriorityOfficiousQueue("Bisection"){ std::cout << "\n"; }
private:
//funkcja wyszukuje metodą połowienia w uporządkowanym zbiorze miejsce, na które należy wstawic nowy element
int BisekcjaDoWstawiania(int L, int R, typ& El) //przez zastosowanie referencji unikamy kopiowań danych
{
int Podzial;
if(R-L<=1)
{
if((*this)[R] < El) return R+1;
else
{
if((*this)[L] < El) return R;
else return L;
}
}
else
 Podzial=L+(R-L)/2;
if((*this)[Podzial] < El) return BisekcjaDoWstawiania(Podzial,R,El); //działanie rekurencyjne
else return BisekcjaDoWstawiania(L,Podzial,El); //działanie rekurencyjne
}
}
void putOfficious(typ& a)
{
int size = getDataSize();
if (size != -1) // jeśli zbiór nie jest pusty
{
int w = BisekcjaDoWstawiania( 0, size, a );
increaseDataSize();
for (int i = size+1; i > w; --i )//tworzenie miejsca na nowy element, przesuwanie o 1 wszystkich elementów z prawej
{
(*this)[i] = (*this)[i-1];
}
(*this)[w] = a; //wstawianie nowego elementu na miejsce docelowe
}
else (*this) += a;
}
//dzięki zastosowaniu konwencji, że wraz ze wzrostem indeksu tablicy rośnie priorytet elementu, oraz wykorzystując własność, iż
po wstawianiu el. zbiór jest zawsze uporządkowany wyjmujemy zawsze skrajmy prawy element i nie musimy po tym porządkować zbioru
typ getOfficious()
{
decreaseDataSize();
Jhhj return (*this)[getDataSize() + 1];
}
};
#endif
Implementacja ta została przetestowana i daje poprawne wyniki. Elementy po wstawieniu są zawsze uporządkowane, a po wyjmowaniu elementu nie tracą
porządku. Wyjmowane są zawsze elementy z największym priorytetem. Wydruk testowy pomijam, wydajnośd będzie badana w dalszej części tekstu.
Należy zauważyd, że wąskim gardłem algorytmu jest pętla przesuwająca o 1 elementy na prawo od wstawianego. Wykonywanych jest wiele kopiowao
danych, a w zastosowanej implementacji tablicy danych czasochłonne są też operacje indeksowania *+. Rozwiązaniem mogło by byd zastosowanie zamiast
tablicy implementacji listowej (to by jednak utrudniło zastosowanie bisekcji i przypuszczalnie zwiększyło liczbę porównao  a więc powinno byd opłacalne dla
złożonego typu elementów gdzie kluczowy jest czas kopiowao, dla prostych elementów niekoniecznie).
II) Implementację kolejki z algorytmem QuickSort stworzyłem wykorzystując szkielet klas i funkcji, na których bazowały inne algorytmy w zadanym
programie testowym oraz wzorując się na implementacji algorytmu QuickSort zaczerpniętej z Wikipedii.
// Kolejka priorytetowa leniwa dzialajaca z użyciem algorytmu QuickSort przy wyjmowaniu elementu
#ifndef QUICKSORT_QUEUE_H
#define QUICKSORT_QUEUE_H
#include "AbstractPriorityQueue.h"
template
class QuickSortQueueLazy : public AbstractPriorityLazyQueue, public SmartDataTable
{
public:
QuickSortQueueLazy() : AbstractPriorityLazyQueue("QuickSort"){ std::cout << "\n"; }
private:
void QuickSortRekur(int L, int R)
{
if( R > L )
{
int i=L;
int j=R;
int v = (R+L)/2; //Wybór osi podziału danych w dużej mierze wpływa na wydajność
do
{
while( i <= j && (*this)[i] < (*this)[v] ) ++i; //poszukiwanie elementów mniejszych niż osiowy
while( j >= i && (*this)[v] < (*this)[j] ) --j; //poszukiwanie elementów większych niż osiowy
if(i <= j)
{
if (i != j) swap(i, j); //Zamiana znalezionych elementów  mniejszego i większego niż osiowy
++i;
--j;
}
}
while (i <= j);
QuickSortRekur(L, j); //Rekurencyjne porządkowanie lewego podzbioru
QuickSortRekur(i, R); //Rekurencyjne porządkowanie prawego podzbioru
}
}
void putLazy(typ& a)
{
(*this) += a;
}
//dzięki zastosowaniu konwencji, że element o najwyższym priorytecie znajduje się w skrajnym prawym indeksie tablicy zamiast w
pierwszym unikamy kopiowania elementu ostatniego na miejsce pierwszego (jak w funkcji GetFirst() z klasy SmartDataTable) i
przez to także zaburzania uporządkowania elementów.
typ getLazy()
{
if(getDataSize() < 0) throw QueueException(QUEUE_EMPTY);
QuickSortRekur(0, getDataSize());
decreaseDataSize();
return (*this)[getDataSize() + 1];
}
};
#endif
Implementacja ta została przetestowana i daje poprawne wyniki. Elementy są sortowane przy wyjmowaniu. Wyjmowane są zawsze elementy z największym
priorytetem. Wydruk testowy pomijam, wydajnośd będzie badana w dalszej części tekstu.
Użycie tego algorytmu powoduje sortowanie za każdym razem całego zbioru danych, podczas gdy potrzebujemy znalez
d jedynie element największy.
Ponieważ dla zbiorów wstępnie uporządkowanych algorytm ten wykonuje mało kopiowao może okazad się dośd wydajny przy niektórych sekwencjach
put/get i szczególnie dla złożonych typów danych. Algorytm zawsze wykonuje wiele porównao.
Na wydajnośd algorytmu duży wpływ ma także wybór punktu osiowego podziału zbioru.
a) Zbadad dla jakich sekwencji put/get podejście leniwe jest lepsze/gorsze/takie samo jak nadgorliwe.
Zaimplementowałem kilka procedur testowych generujących różne ciągi operacji put/get (ich kody z
ródłowe pomijam w sprawozdaniu jako nieistotne). Dla
każdej z procedur badałem liczbę kopiowao i porównao we wszystkich implementacjach kolejki priorytetowej, w wersji nadgorliwej i leniwej oraz dodatkowo
dla 2 własnych implementacji z podpunktu f) dwiczenia.
Testy zautomatyzowałem poprzez użycie polimorfizmu i dynamicznego tworzenia odpowiednich klas kolejki. Dokładniejszy opis jednak pomijam, jako że nie
jest tematem zadania i nie wpływa na wyniki.
A) Domyślnie zaimplementowana procedura testowa
put(8), put(2), put(5), put(4), put(1), put(7), put(6), put(11), put(3), get(), put(3), put(12), put(1), put(5), put(11), get()
350
300
207
250
200
79
Kopiowania
150
Porównania
31
64
120
100
55
104 104
80
65
54
80
44
50
53
26
32
31
22
20 20
0
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
Jak widad dla przykładowego ciągu działao, gdzie przeważają operacje wstawiania elementów różne implementacje algorytmów zachowują się w bardzo
zróżnicowany sposób. Wyraz
nie lepsze wyniki uzyskują wersje leniwe algorytmów (chod dla kopca różnica jest niewielka, a pod względem liczby kopiowao jest
nawet o 1 gorsza niż nadgorliwa).
B) 100x put(i), 100x get(), gdzie i to kolejno rosnące liczby
35000
30000
20625
497
25000
20000
9916
Kopiowania
12381
15000
Porównania
26838
793
10000
3255
2020
693
5000
10001
9801 9801
3080
5737
4950 4950 5050
659
1291
0 201
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
Gdy najpierw wypełniamy kolejkę, a potem w całości ją opróżniamy zdecydowanie najlepszym okazał się algorytm bisekcji. Najlepiej pod względem
liczby kopiowao wypada algorytm QuickSort, jednak charakteryzuje się ogromną liczbą porównao (jak przewidziano w teorii).
Oprócz implementacji na kopcu lepszą wydajnośd posiadają wersje leniwe algorytmów.
C) 100x put(i), 100x get(), gdzie i to kolejno malejące liczby
30000
350
25000
20000
15000
5582
Kopiowania
26817
Porównania
3226
646
10000
5482
3126
5150
1651
546
5000
10001
9801 9801
5600
5050
4950 4950
1751
666
944
0
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
Jak widad nie tylko kolejnośd operacji put/get, ale także wartości wstawianych elementów mają znaczny wpływ na wydajnośd algorytmów.
Wystarczyło zamienid kolejnośd wstawianych wartości aby znacznie wzrosła liczba kopiowao w algorytmie bisekcji i znacząco spadła w pozostałych
(szczególnie w implementacjach bąbelkowych i w turnieju nadgorliwym).
D) put(), get(), put(), get(), put(), get()& (100xput, 100xget)
1200
989
1000
889
793 794
800
693 694
793
600
693 Kopiowania
Porównania
400
200
200
200
299
199 200
99 99 99 99 99 99
0
0
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
W przypadku podanej sekwencji zawsze mamy w tablicy najwyżej 1 element  praktycznie nie ma więc czego sortowad, wykonywane działania są w
większości niepotrzebnym narzutem operacji. Jak widad przeważają operacje kopiowania. W przypadku zaimplementowanych przeze mnie funkcji są one
resztkowe (wynikają z działania konstruktorów kopiujących przy przekazywaniu elementów między funkcjami, a nie z samego algorytmu porządkującego).
Warto zauważyd, że algorytm bisekcji nie wykonuje w ogóle porównao. Wszystkie wyniki w przypadku tej sekwencji są właściwie niewrażliwe na wstawiane
wartości.
We wszystkich przypadkach nieznacznie lepsze okazały się wersje leniwe algorytmów.
E) put(), put(), put(), get(), put(), put(), put(), get()& (300xput, 100xget, nie wszystkie elementy wyjęte, rosnący rozmiar tablicy, wartości rosnące)
160000
140000
104038
120000
100000
80000
Kopiowania
Porównania
700
30997
60000
1594
40000
31100
63949
15750
20000 40400
40000 40000
5812
900
12808
401
10100 7337 10100 10200
2793
2301
0
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
Wyniki mają charakter bardzo zbliżony do tych z podpunktu B)
F) put(), put(), put(), get(), put(), put(), put(), get()& (300xput, 100xget, nie wszystkie elementy wyjęte, rosnący rozmiar tablicy, wartości malejące)
120000
100000
30082
80000
35615
60000
Kopiowania
Porównania
1006
7636
40000
78017
20000 40400
40000 40000
29804
12182
900
5724 2227
1378
10960
10100 10100 10200
2378
0
2354
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
Jak widad również w przypadku tej sekwencji algorytmy są czułe na postad wartości elementów. Zmiany są podobne jak pomiędzy podpunktem B) i C)
z tą jednak różnicą, że w przypadku algorytmu QuickSort liczba kopiowao nie zmalała, a znacznie wzrosła.
G) Losowa sekwencja, z równym prawdopodobieostwem put() i get(), wartości dla put() losowe.
9000
8000
5831
7000
6000
5000
Kopiowania
4000
Porównania
3000
1496
788
515
2000
1495
1234
948
2268
1000 2033
846
1749 1736
574
832
632
433 502
468
393
231
0
Turniej Turniej Kopiec Kopiec Babelkowy Bąbelkowy Selekcja Selekcja Bisekcja QuickSort
Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwy Leniwy Nadgorliwa Leniwa Nadgorliwa Leniwy
W przypadku losowym  średnim uzyskane wyniki są podobne do tych z podpunktu A) (co nie dziwi, gdyż tam sekwencja była dośd przypadkowa) i
dośd dobrze uśredniają wyniki zebrane z testów innych sekwencji.
W każdym przypadku lepsze wyniki uzyskują wersje leniwe algorytmów.
2) Wnioski koocowe
Ponieważ  nadgorliwośd jest gorsza od faszyzmu w zdecydowanej większości przypadków nie warto stosowad algorytmów nadgorliwych. Ich leniwe
odpowiedniki są w niektórych przypadkach znacznie bardziej wydajne. Wyjątkiem jest jedynie implementacja na kopcu przy niektórych (uporządkowanych)
sekwencjach danych.
Istotnym wnioskiem jest, iż dane implementacje w sposób znaczny potrafią reagowad nie tylko na kolejnośd operacji put/get, ale także na kolejne wartości
wkładanych elementów.
Zaimplementowany przeze mnie algorytm używający QuickSort w większości przypadków wymaga niewielu kopiowao danych lecz zawsze używa wielu
porównao. W niektórych warunkach wymaga też jednak znacznej ilości kopiowao, dlatego w ogólnym rozrachunku wypada słabo.
Algorytm z bisekcją daje zadowalające wyniki, jednak jest silnie czuły pod względem ilości kopiowao na postad danych, zwłaszcza wartości elementów.
Zdecydowanie najgorzej spisują się algorytmy bąbelkowe; wersja nadgorliwa wręcz fatalnie.
Turniej, zwłaszcza w wersji leniwej prezentuje przyzwoitą wydajnośd. Jego zaletą jest też stosunkowo mała wrażliwośd na sekwencje/wartości elementów.
Jeszcze lepsze wyniki i mniejszą podatnośd na postad danych uzyskuje implementacja na kopcu, szczególnie wersja nadgorliwa. Dla niektórych regularnych
sekwencji posiada najlepsze wyniki, jednak w przypadku średnim niekoniecznie.
W ogólnym rozrachunku najlepszą implementacja kolejki priorytetowej jest selekcja, ze szczególnym wskazaniem na wersję leniwą. Charakteryzuje się dośd
stabilnymi, niskimi ilościami operacji, a co ważne występuje szczególnie mało kopiowao, które zwykle są bardziej czasochłonne niż porównania.
Wybór do własnych zastosowao odpowiedniej implementacji kolejki priorytetowej nie jest zadaniem łatwym. W zasadzie nie da się wskazad ogólnie najlepszej
implementacji. Różne algorytmy zyskują w różnych warunkach, dlatego wybierając implementację należy rozważyd wiele czynników, takich jak najczęstsze
sekwencje operacji, wartości wstawianych elementów, czas elementarnych operacji kopiowania i porównywania (zależny od typu przechowywanych
elementów). W wielu przypadkach warto rozważyd także implementację inną niż na tablicy, np. z użyciem listy. Może ona dawad znacznie lepsze wyniki.