| Wykonawca: |
|---|
| Laboratorium Podstaw Informatyki |
| Temat: |
| Rok Akademicki |
2006/2007 Semestr Letni |
Przygotować zbiór z danymi tekstowymi.
Za pomocą programu dostępnego na laboratorium przygotowałem zestaw danych 150 losowo wybranych liczb z przedziału 0 – 999 i zapisałem w pliku dane.txt. Następnie za pomocą programu wygenerowaliśmy plik szukane.txt, który zawierał 75 losowo wybranych liczb z pliku dane.txt. Dzięki temu uzyskaliśmy pliki z danymi testowymi do dalszej części laboratorium.
Przeprowadzić eksperymenty z metodą przeszukiwania sekwencyjnego dla danych przypadkowych i dla danych posortowanych. Porównać wyniki.
| DANE | ILOŚĆ DANYCH | ILOŚĆ SZUKANYCH | MIN | MAX | ŚREDNIA |
|---|---|---|---|---|---|
| przypadkowe | 150 | 75 | 1 | 145 | 69,96 |
| posortowane | 150 | 75 | 4 | 144 | 79,33 |
Przewidywałem, iż oba wyniki będą podobne, ponieważ w przypadku przeszukiwania sekwencyjnego kolejność podanych danych nie ma znaczenia. Widać jednak doskonale, iż dla posortowanych danych przeszukiwanie sekwencyjne nie jest lepsze niż dla danych przypadkowych, a jak widać na przykładzie moich danych zdarza się i tak, że uzyskujemy wynik gorszy. Przyczyną takiego stanu rzeczy może być spora ilość danych z większego przedziału co powoduje dłuższe przeszukiwanie sekwencyjne.
Te same testy przeprowadzić dla wyszukiwania metoda podziałów dychotomicznych. Porównać uzyskane wyniki.
| DANE | ILOŚĆ DANYCH | ILOŚĆ SZUKANYCH | MIN | MAX | ŚREDNIA |
|---|---|---|---|---|---|
| posortowane | 150 | 75 | 2 | 8 | 6,12 |
Jak widać metoda podziałów dychotomicznych w przeciwieństwie do przeszukiwania sekwencyjnego wykorzystuje posortowanie danych, dzięki czemu jest o wiele skuteczniejsza. Wyniki potwierdziły więc moje przewidywania.
Przeprowadzić eksperymenty z drzewami binarnymi.
| DANE | ILOŚĆ DANYCH | ILOŚĆ SZUKANYCH | MIN | MAX | ŚREDNIA |
|---|---|---|---|---|---|
| zwykłe drzewo | 150 | 75 | 1 | 13 | 8,65 |
| drzewo idealnie wyważone | 31 | 15 | 2 | 5 | 4,33 |
Niestety program, którym posługiwaliśmy się na laboratorium nie miał opcji tworzenia drzewa idealnie wyważonego. Dlatego głównym zadaniem na laboratorium było stworzenie takiego drzewa z 31 liczb. (Zadanie 5) Następnie za pomocą programu stworzyłem plik szukane1.txt, w którym zostało umieszczonych 15 losowych liczb z stworzonego przeze mnie drzewa. Dzięki czemu mogliśmy przeprowadzić eksperyment dla drzewa idealnie wyważonego, natomiast dla zwykłych drzew wykorzystaliśmy dane i szukane wygenerowane na początku laboratorium.
Średnia liczba porównań dla drzewa idealnie wyważonego jest znacząco mniejsza w moim przypadku nawet dwukrotnie mniejsza. Wyszukiwanie w drzewie idealnie wyważonym jest zdecydowanie szybsze, ponieważ zapewnia przeszukiwanie minimalnej liczby poziomów. W skrajnym przypadku przeszukiwanie zwykłego drzewa może się sprowadzić do przeszukiwania sekwencyjnego listy.
Określić przykładową kolejność wprowadzenia do drzewa 31 liczb tak, aby uzyskać dokładnie wyważone drzewo binarne.
Aby uzyskać idealnie wyważone drzewo binarne należy wprowadzać dane poziomami od prawej aż do liści. Kolejność wprowadzania danych dla mojego drzewa wyglądała następująco: 16, 8, 24, 4, 12, 20, 28, 2, 6, 10, 14, 18, 22, 26, 30, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31. Dzięki czemu uzyskałem idealnie wyważone drzewo z wartościami 1-31.
Przeprowadzić eksperymenty dotyczące wyszukiwania w B-drzewach, dla różnych wielkości strony.
| M | DOSTĘPY DO PAMIĘCI | DOSTĘPY DO DYSKU |
|---|---|---|
| MIN | MAX | |
| 2 | 3 | 9 |
| 5 | 3 | 8 |
| 8 | 1 | 8 |
| 10 | 2 | 8 |
| 12 | 1 | 8 |
| 20 | 3 | 8 |
Wyszukiwanie przeprowadziłem dla różnych rozmiarów stron (M) B-drzewa. Najbardziej optymalny rozmiar strony spośród przebadanych przeze mnie wynosi M=8.
Obliczyć minimalną i maksymalną liczbę elementów jaką można umieścić w B-drzewie klasy T(h,m).
Dla maksymalnej liczby elementów:
h=1 2m 2m
h=2 2m+2m(2m+1) 2m(1+(2m+1))
h=3 2m+2m(2m+1)+2m(2m+1)(2m+1) 2m(1+(2m+1)+(2m+1)2)
$$T_{\text{MAX}}\mathrm{(h,m) = 2m}\sum_{i = 0}^{h - 1}{(2m + 1)}^{i}$$
Dla minimalnej liczby elementów:
h=1 1
h=2 1+2m 1+2m
h=3 1+2m+2m(m+1) 1+2m(1+(m+1))
h=4 1+2m+2m(m+1)+2m(m+1)2 1+2m(1+(m+1)+(m+1)2)
$$T_{\text{MIN}}\mathrm{(h,m) =}\left\{ \begin{matrix}
1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathrm{h = 1} \\
1 + 2m\sum_{i = 0}^{h - 2}{(m + 1)}^{i}\text{\ \ \ \ \ \ \ \ \ \ }\mathrm{h > 1} \\
\end{matrix} \right.\ $$
Przeprowadzić eksperymenty dotyczące wyszukiwania w B*-drzewach, dla różnych wielkości strony.
| M | DOSTĘPY DO PAMIĘCI | DOSTĘPY DO DYSKU |
|---|---|---|
| MIN | MAX | |
| 2 | 5 | 9 |
| 5 | 5 | 8 |
| 10 | 4 | 8 |
| 20 | 4 | 8 |
| 30 | 3 | 8 |
Wyszukiwanie przeprowadziłem dla różnych rozmiarów stron (M) B-drzewa. Najbardziej optymalny rozmiar strony spośród przebadanych przeze mnie wynosi M=20.
Porównać wyniki uzyskane dla B-drzew i B*-drzew.
Wyniki wyszukiwania dla B*-drzew były nieznacznie wolniejsze, ponieważ w B*-drzewach na najniższym poziomie znajdują się wszystkie elementy drzewa przez co drzewo jest większe co wydłuża przeszukiwanie.
Przeprowadzić eksperymenty dotyczące wstawiania danych do tablicy mieszającej.
Dla rozmiaru tablicy M=200, funkcjami mieszającymi i funkcjami rozwiązywania kolizji przeprowadziłem następujące wyszukiwania, dla danych wygenerowanych na początku laboratorium:
| FUNKCJA MIESZAJĄCA | FUNKCJA ROZWIĄZYWANIA KOLIZJI | MIN | MAX | ŚREDNIA |
|---|---|---|---|---|
| dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 1 | 1 | 7 | 1,44 |
| dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 3 | 1,28 |
| dzielenie przez rozmiar tablicy | podwójne mieszanie zależne | 1 | 6 | 1,47 |
| dzielenie przez rozmiar tablicy | podwójne mieszanie niezależne | 1 | 5 | 1,43 |
| mieszanie Fibonaciego | podwójne mieszanie niezależne | 1 | 9 | 1,73 |
| podział, składanie, dzielenie | podwójne mieszanie niezależne | 1 | 5 | 1,42 |
| wycięcie 3 cyfr i normalizacja | podwójne mieszanie niezależne | - | - | - |
Dla funkcji mieszającej wycięcie 3 cyfr i normalizacja i dla funkcji rozwiązywania kolizji podwójne mieszanie niezależne wystąpił błąd podczas wstawiania danych, ponieważ funkcja rozwiązywania kolizji weszła w zapętlenie i nie była w stanie wstawić wszytki och danych do tablicy.
Najmniejsza ilość kolizji dla funkcji mieszającej dzielenie przez rozmiar tablicy wystąpiła dla funkcji rozwiązywania kolizji sondowanie liniowe z krokiem 7, miała ona jednocześnie najmniej kolizji spośród przetestowanych przeze mnie funkcji mieszających, natomiast najmniejszą liczbę kolizji dla funkcji rozwiązywania kolizji podwójne mieszanie niezależne odnotowałem dla funkcji mieszającej podział, składanie, dzielenie.
Następnie zbadałem wpływ rozmiaru tablicy na liczbę kolizji występujących podczas wstawiania dla najlepszej spośród przebadanych przeze mnie funkcji mieszającej dzielenie przez rozmiar tablicy i funkcji rozwiązywania kolizji sondowanie liniowe z krokiem 7.
| M | FUNKCJA MIESZAJĄCA | FUNKCJA ROZWIĄZYWANIA KOLIZJI | MIN | MAX | ŚREDNIA |
|---|---|---|---|---|---|
| 150 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 131 | 8,04 |
| 160 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 18 | 2,37 |
| 170 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 25 | 2,05 |
| 180 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 29 | 2,20 |
| 190 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 6 | 1,43 |
| 200 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 3 | 1,28 |
| 210 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 16 | 1,63 |
| 250 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 12 | 1,93 |
| 300 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 3 | 1,29 |
| 350 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 4 | 1,08 |
| 400 | dzielenie przez rozmiar tablicy | sondowanie liniowe z krokiem 7 | 1 | 2 | 1,11 |
Dla zadanej przeze mnie funkcji mieszającej i funkcji rozwiązywania kolizji trudno było mi teoretycznie przewidzieć jaki wpływ będzie miał rozmiar tablicy, postanowiłem więc to zbadać. W moim przypadku zwiększanie rozmiaru tablicy, determinuje malejącą liczbę kolizji. Jak widać w przypadku większej tablicy, ilość kolizji ma tendencje malejącą, chociaż nie zawsze tak jest. Przykładem są rozmiary tablic M=180, M=210, M=250 i M=400. Dla nich jak widać występuje wieksza liczba kolizji niż dla mniejszych od nich tablic, co pokazuje ze w przypadku tej funkcji mieszającej i funkcji rozwiązywania kolizji zdarzają się rozmiary tablic, które nie pasują do końca wygenerowanym przeze mnie danym. Najlepszy rozmiar spośród przebadanych przeze mnie wyniósł M=350. Całkiem niezły wynik uzyskałem dla M=200, dlatego dla tych danych może warto wybrać ten właśnie rozmiar tablicy, ponieważ tablica o rozmiarze M=350 pochłania prawie dwukrotnie więcej pamięci, ale to już zależy od użytkownika, czy bardziej zależy mu na wyszukiwaniu czy na oszczędności pamięci.