Krzysztof Baszczok 25.05.2009

Metody dostępu do danych

Zad 1.

Dane 1 – 100 losowo wygenerowanych liczb z zakresu 0-999

Dane 2 – 50 losowo wygenerowanych liczb z Dane 1

Zad 2.

Dla nieposortowanych: Min = 1, Max = 97, średnio 55,66

Dla posortowanych: Min = 9, Max = 98, średnio 52,38

Dla posortowanych danych średni czas nieznacznie się skrócił, ale za to min i max wzrosły.

Zad 3.

Metody podziałów dychotomicznych: Min = 2, Max = 7, średnio 5,28

Metoda podziałów daje o wiele bardziej zadowalające wyniki.

Zad 4.

Drzewo binarne dokładnie wyważone: Min = 1, Max = 9, średnio 2,08

Drzewo binarne: Min = 1, Max = 10, średnio 6,66

Drzewo dokładnie wyważone daje max równą jego wysokości, zaś w drugim wypadku daje całkiem inną wartość. W najgorszym wypadku powstanie lista co da max równego długości listy (100).

Zad 5.

Kolejność wprowadzania 31 liczb dla uzyskania drzewa binarnego idealnie wyważonego

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

Zad 6.

B-drzewo:

m=2

Dostępy do pamięci: Min = 1, Max = 7, średnio 5,28.

Dostępy do dysku: Min = 1, Max = 4, średnio 3,6.

m=5

Dostępy do pamięci: Min = 2, Max = 8, średnio 5,66.

Dostępy do dysku: Min = 2, Max = 3, średnio 2,76.

m=7

Dostępy do pamięci: Min = 1, Max = 8, średnio 5,98.

Dostępy do dysku: Min = 1, Max = 2, średnio 1,92.

m=10

Dostępy do pamięci: Min = 3, Max = 8, średnio 5,84.

Dostępy do dysku: Min = 1, Max = 2, średnio 1,98.

Najlepszy dostęp do pamięci otrzymano dla m=10, do dysku m=7.

Zad 7.

N_min=2(m+1)^h-1-1

N_max = (2m+1)^h-1

Zad 8.

B*-drzewo

m=2

Dostępy do pamięci: Min = 5, Max = 8, średnio 6,68.

Dostępy do dysku: Min = 4, Max = 4, średnio 4.

m=5

Dostępy do pamięci: Min = 4, Max = 8, średnio 6,58.

Dostępy do dysku: Min = 3, Max = 3, średnio 3.

m=10

Dostępy do pamięci: Min = 4, Max = 8, średnio 6,44.

Dostępy do dysku: Min = 2, Max = 2, średnio 2.

Zarówno dostęp do pamięci i do dysku dały najlepszy wynik dla m=10.

Zad 9.

Dla tych danych wyniki są całkiem podobne, jednak lepsze otrzymano dla B-drzewa.

Zad 10.

Rozmiar tablicy: 200

Funkcja mieszająca:

• dzielenie przez rozmiar tablicy: Min = 1, Max = 9, średnio 2,08

• mieszanie Fibonacciego: Min = 1, Max = 8, średnio 2,12

• wycięcie 3 cyfr klucza i normalizacja: Min = 1, Max = 97, średnio 55,66

• podział, składanie i dzielenie: Min = 1, Max = 9, średnio 2,08

Do dalszych badań wybrano dzielenie przez rozmiar tablicy

Funkcja rozwiązywania kolizji:

• sondowanie liniowe z krokiem 1: Min = 1, Max = 9, średnio 2,08

• sondowanie liniowe z krokiem 7: Min = 1, Max = 3, średnio 1,36

• podwójne mieszanie zależne: Min = 1, Max = 4, średnio 1,86

• podwójne mieszanie niezależne: Min = 1, Max = 4, średnio 1,5

Rozmiar tablicy: 150

Funkcja mieszająca:

• dzielenie przez rozmiar tablicy: Min = 1, Max = 28, średnio 6,42

• mieszanie Fibonacciego: Min = 1, Max = 17, średnio 2,22

• wycięcie 3 cyfr klucza i normalizacja: Min = 1, Max = 97, średnio 55,66

• podział, składanie i dzielenie: Min = 1, Max = 28, średnio 6,42

Do dalszych badań wybrano dzielenie przez rozmiar tablicy

Funkcja rozwiązywania kolizji:

• sondowanie liniowe z krokiem 1: Min = 1, Max = 28, średnio 6,42

• sondowanie liniowe z krokiem 7: Min = 1, Max = 7, średnio 2,4

• podwójne mieszanie zależne: Min = 1, Max = 7, średnio 2,32

• podwójne mieszanie niezależne: Min = 1, Max = 7, średnio 2,34

Zmniejszenie rozmiaru tablicy powoduje wydłużenie się czasu szukania danych, jedynie dla funkcji wycinającej 3 cyfry klucza i normalizacja nie zależy od rozmiaru tablicy.