Wykonawca: Przemysław Szyngiera
Laboratorium Podstaw Informatyki
Temat:	Metody dostępu do danych						Nr.lab.: 5
Rok akademicki	termin	Rodz. studiów	grupa	Data lab.	Data oddania sprawozdania	prowadzący		ocena
2007/2008 semestr letni	wtorek 8-11	Dzienne	4	4.04	18.04	Dr Robert Brzeski

Zadanie 1. Przygotować zbiór z danymi testowymi.

Korzystając w programie z funkcji Generuj stworzono następujące zbiory danych:

• 31 elementów z przedziału od 10000 do 2147483647(max)

• 500 elementów z przedziału od 0 do 999

• 31 elementów z przedziału od 0 do 99

Zadanie 2. Przeprowadzić eksperymenty z metodą przeszukiwania sekwencyjnego dla danych przypadkowych, dla danych posortowanych. Porównać wyniki. W wyniku powinny się znaleźć tablica z danymi, liczba

przeprowadzonych prób wyszukania, średnia liczba testów (eksperymentalna), minimalna i maksymalna

liczba testów.

Zbiór danych wygenerowanych z przedziału 0-99: 79, 7, 45, 85, 49, 75, 82, 8, 22, 80, 78, 48, 22, 87, 24, 86, 93, 41, 84, 1, 17, 26, 6, 42, 83, 43, 36, 96, 62, 17, 52

Szukany element	Liczba prób wyszukania dla danych przypadkowych	Liczba prób wyszukania dla tych samych danych: posortowanych
1	20	1
7	2	3
17	21	5
26	22	10
52	31	18
78	11	21
79	1	22
85	4	27
86	16	28
98	31	31
Średnia liczba testów:	15,9		15,36
Minimalna liczba testów:	1		1
Maksymalna liczba testów:	31		31

Wnioski: Minimalna i maksymalna liczba testów jest taka sama zarówno dla danych przypadkowych jak i tych samych danych posortowanych. Natomiast średnia liczba testów zmalała
w przypadku danych posortowanych. Dla danych posortowanych im większa wyszukiwana jest liczba, tym więcej wymaga ona testów.

Zadanie 3. Te same testy przeprowadzić dla wyszukiwania metodą podziałów dychotomicznych. Porównać

uzyskane wyniki.

Szukany element	Liczba prób wyszukania metodą podziałów dychotomicznych
1	5
7	4
17	5
26	5
52	5
78	4
79	4
85	5
86	4
98	5
Średnia liczba testów:	4,45
Minimalna liczba testów:	3
Maksymalna liczba testów:	5

Wnioski: Wyniki dla tej metody są zdecydowanie najlepsze: zmniejszyła się znacznie średnia
i maksymalna liczba testów. Niezależnie od doboru danych, tą metodą uzyskamy lepsze wyniki ponieważ ma ona złożoność obliczeniową O(log n) natomiast metoda z poprzedniego zadania złożoność liniową.

Zadanie 4. Przeprowadzić eksperymenty z drzewami binarnymi. Porównać uzyskane wyniki dla „zwykłych” drzew (bez wyważenia) i drzew dokładnie wyważonych. Czy średnia liczba porównań w obu przypadkach

różni się znacząco ?

Przeszukiwanie drzewa dokładnie wyważonego - stworzonego w zadaniu 5

Szukany element	Liczba porównań
1	5
3	5
4	3
6	4
7	5
8	2
10	4
11	5
15	5
16	1
17	5
18	4
19	5
20	3
22	4
24	2
27	5
31	5
Średnia liczba porównań:	4,2

Przeszukiwanie drzewa niewyważonego o postaci:

1

6

7

8

17

17

22

22

24

26

36

41

42

43

45

48

49

52

62

75

78

79

80

82

83

84

85

86

87

93

96

Poszukiwana liczba	Liczba porównań
1	3
6	4
6	4
17	6
22	5
22	5
24	7
35	6
36	10
41	8
42	9
43	10
55	8
62	6
79	1
79	1
80	4
80	4
82	3
82	3
83	5
85	2
86	4
87	3
96	5
Średnia liczba porównań:	5,04

Wnioski: Dla drzewa dokładnie wyważonego średnia liczba porównań jest znacznie mniejsza niż dla drzewa niewyważonego - około 25%.

Zadanie 5. Określić przykładową kolejność wprowadzania do drzewa 31 liczb tak by uzyskać dokładnie wyważone drzewo binarne.

Przykładowa kolejność wprowadzania do drzewa 31 liczb tak aby uzyskać wyważone drzewo binarne:

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

W wyniku powstaje następujące drzewo:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

Zadanie 6. Przeprowadzić eksperymenty dotyczące wyszukiwania w B-drzewach, dla różnych wielkości strony.

Określić optymalny ze względu na czas wyszukiwania rozmiar strony.

29 wygenerowanych danych testowych:

18, 26, 26, 43, 47, 50, 102, 231, 305, 407, 409, 433, 481, 558, 578, 617, 625, 628, 689, 726, 737, 781, 905, 906, 910, 960, 966, 997, 1410

Wielkość strony M	Minimalna liczba dostępów do pamięci	Maksymalna liczba dostępów do pamięci	Średnia liczba dostępów do pamięci	Minimalna liczba dostępów do dysku	Maksymalna liczba dostępów do dysku	Średnia liczba dostępów do dysku
1	1	11	6,62	1	7	5,24
2	4	10	7,31	3	5	4,38
3	4	10	7,83	2	4	3,68
4	3	11	7,38	2	4	3,59
5	5	10	7,48	2	3	2,76
6	3	10	7,66	2	3	2,83
7	4	10	7,66	2	3	2,83
8	2	10	7,93	2	3	2,9
9	1	10	7,59	1	3	2,86

Wnioski: Dla powyższych danych, optymalna liczba elementów na stronie ze względu na średnią liczbę dostępów do pamięci wynosi 1, a ze względu na średnią liczbę dostępów do dysku wynosi 5.

Zadanie 7. Obliczyć minimalną i maksymalną liczbę elementów jakie można umieścić w B-drzewie
klasy t(h,m).

Wzór na liczbę elementów w B-drzewie :

h - liczba poziomów drzewa,

m_i - liczba elementów na stronie na poziomie i.

Maksymalna liczba elementów, jakie można umieścić w B-drzewie klasy t(h,m) :

Minimalna liczba elementów, jakie można umieścić w B-drzewie klasy t(h,m) :

Zadanie 8. Przeprowadzić eksperymenty dotyczące wyszukiwania w B*-drzewach, dla różnych wielkości strony. Określić optymalny ze względu na czas wyszukiwania rozmiar strony.

Eksperymenty przeprowadzane były na wygenerowanych danych z zadania 6.

Wielkość strony M	Minimalna liczba dostępów do pamięci	Maksymalna liczba dostępów do pamięci	Średnia liczba dostępów do pamięci	Minimalna liczba dostępów do dysku	Maksymalna liczba dostępów do dysku	Średnia liczba dostępów do dysku
1	7	11	9,48	7	7	7
2	7	12	9,03	5	5	5
3	6	10	8,52	4	4	4
4	7	10	8,48	3	3	3
5	7	10	8,83	3	3	3
6	6	10	8,62	3	3	3
7	6	10	8,20	3	3	3
8	6	10	8,24	3	3	3

Wnioski: Najmniejsza ilość dostępów do pamięci wystąpiła dla wielkości strony równej 7 a do dysku uzyskano dla wielkości strony równej większej od 3. Zatem najbardziej optymalny ze względu na czas wykonania jest rozmiar strony równy 7.

Zadanie 9. Porównać wyniki uzyskane dla B-drzew i B*-drzew.

	Średnia ilość dostępów do pamięci	Minimalna ilość dostępów do pamięci	Średnia ilość dostępów do dysku	Minimalna ilość dostępów do dysku
B-drzewo	7,49	6,62	3,45	2,76
B*-drzewo	8,76	8,20	3,87	3,00

Wnioski: Wyniki uzyskane dla B-drzewa są pod każdym względem lepsze niż wyniki uzyskane dla B*-drzewa.

Zadanie 10. Przeprowadzić eksperymenty dotyczące wstawiania danych do tablicy mieszającej. Sprawdzić wpływ rozmiaru tablicy, wybranej funkcji mieszającej i funkcji rozwiązywania kolizji na liczbę kolizji

występujących podczas wstawiania. Porównać uzyskane wyniki z przewidywaniami teoretycznymi.

Rozmiar tablicy M	Minimalna liczba kolizji	Maksymalna liczba kolizji	Średnia liczba kolizji
31	1	21	4,13
32	1	24	3,51
35	1	21	3,06
39	1	9	2,38
42	1	7	2,12
44	1	6	2,06
45	1	8	1,48
50	1	5	1,74
75	1	2	1,10
100	1	4	1,30
150	1	2	1,06
200	1	2	1,10

Wnioski: Najmniejsza liczba kolizji wystąpiła przy rozmiarze tablicy równym 150, jednak porównywalny wynik wystąpił już przy rozmiarze 75. Na podstawie wyników można stwierdzić, że najlepsze wyniki, gdzie średnia liczba kolizji jest niska przy w miarę niskim rozmiarze tablicy: 75 (około 2 razy większa niż ilość wstawianych elementów). Jednak zadawalający wynik występował już przy rozmiarach: 44 i 45, gdzie maksymalna i średnia liczba kolizji była niska.

Wpływ funkcji mieszającej na liczbę kolizji:

Funkcja rozwiązywania kolizji: sondowanie liniowe z krokiem 1

Rozmiar tablicy: 35

Funkcja mieszająca	Minimalna liczba kolizji	Maksymalna liczba kolizji	Średnia liczba kolizji
Wycięcie 3 cyfr klucza i normalizacja	1	14	3,16
Podział, składania i dzielenie	1	14	2,32
Dzielenie przez rozmiar tablicy	1	21	3,06
Mieszanie Fibonacciego	1	15	2,54

Wnioski: Najlepszą funkcją mieszającą dla rozmiaru tablicy 35 jest: podział, składanie
i dzielenie. Troche gorsze wyniki osiągnęła funkcja mieszająca: mieszanie Fibonacciego.

Wpływu rodzaju funkcji rozwiązywania kolizji na liczbę kolizji:

Funkcja mieszająca: mieszanie Fibonacciego.

Rozmiar tablicy: 40

Rodzaj funkcji rozwiązywania kolizji	Minimalna liczba kolizji	Maksymalna liczba kolizji	Średnia liczba kolizji
Sondowanie liniowe z krokiem 1	1	6	1,87
Sondowanie liniowe z krokiem 7	1	20	3,68
Podwójne mieszanie zależne	1	7	2,23
Podwójne mieszanie niezależne	1	6	1,90

Wnioski: Najlepszy wynik osiągnęła funkcja rozwiązywania kolizji: sondowanie liniowe z krokiem 1 i bardzo podobny wynik do najlepszego: podwójne mieszanie niezależne. Najgorszy wynik uzyskało sondowanie liniowe z krokiem 7.

---