Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/02/27 19:40] 127.0.0.1 edycja zewnętrzna |
pl:dydaktyka:asd:cwiczenia:2012-hashing [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| ====== Tablice haszujące ====== | ====== Tablice haszujące ====== | ||
| - | Termin zajęć: 10/11 maj 2011 | + | Termin zajęć: 8./9. maja 2012 |
| - | **Do przygotowania teoria na temat:** | + | ===== Do przygotowania - teoria na temat: ===== |
| - Rodzaje haszowania | - Rodzaje haszowania | ||
| * haszowanie bezpośrednie | * haszowanie bezpośrednie | ||
| Linia 14: | Linia 14: | ||
| * Metoda adresowania otwartego | * Metoda adresowania otwartego | ||
| - | ===== Przykładowe zadania ===== | + | ===== Do pobrania: ===== |
| - | Poniżej mają Państwo przykładowe zadania z haszowania. W razie znalezienia błędów, prosimy o informację. | + | Proszę pobrać archiwum {{:pl:dydaktyka:asd:cwiczenia:hashing.zip|}}, w którym znajdują się pliki potrzebne do wykonania ćwiczeń na zajęciach. |
| - | **Zadanie 1** \\ | + | Oto krótki opis plików: |
| - | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar ''m=7'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = x*4''. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''5, 3, 7, 10, 2''. \\ | + | * ''finduniversumsize.cpp'' - program obliczający optymalną wielkość tablicy haszującej na podstawie przewidywanej ilości danych i średniej długości łańcucha. |
| - | **Rozwiązanie** \\ | + | * ''findnextprime.cpp'' - program wyszukujący kolejną liczbę pierwszą. |
| - | * ''h(k,i) = (h'(k)+i)%m'' | + | * ''hchain.h'' + ''hchain.cpp'' - moduł zawierający klasę implementującą tablicę haszującą z łańcuchową metodą rozwiązywania konfliktów. |
| - | * ''h'(k) = k%m'' | + | * ''hopen.h'' + ''hopen.cpp'' - moduł zawierający klasę implementującą tablicę haszującą z metodą adresowania otwartego. Moduł ten nie wspiera poprawnie usuwania/usuniętych wartości - uzupełnienie będzie jednym z zadań. |
| - | * ''TAB = 7, 10, 2, NIL, NIL, 3, 5'' | + | * ''mainmodular.cpp'' - niezobowiązujący plik pokazujący przykładowe wykorzystanie klas. |
| - | **Zadanie 2** \\ | + | Proszę zapoznać się ze strukturą i działaniem poszczególnych klas, przetestować kod i w miarę możliwości przynieść na zajęcia laptopy wraz z wszystkimi plikami (można umówić się na pracę w parach/trójkach i na zajęciach pracować we 2-3 osoby przy jednym komputerze). |
| - | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar ''m=7'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = 3x+1''. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''2, 5, 9, 1, 3''. \\ | + | |
| - | **Rozwiązanie** \\ | + | |
| - | * ''h(k,i) = (h'(k)+i)%m'' | + | |
| - | * ''h'(k) = k%m'' | + | |
| - | * ''TAB = 2, 9, 5, 3, 1, NIL, NIL'' | + | |
| - | **Zadanie 3** \\ | + | ===== Ćwiczenia i zadania implementacyjne ===== |
| - | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą kwadratowego adresowania otwartego ''h(k,i) = (h'(k) + i² + i)%m''. Zakładamy że tablica ma rozmiar ''m=8'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = 2x+1''. Przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''2.5, 2, 9, 5, 1''. \\ | + | <WRAP center round info 60%> |
| - | **Rozwiązanie** \\ | + | Punkty oznaczone 8-) należy samodzielnie wykonać w domu, pozostałe punkty stanowią opis, wprowadzenie, zachętę do samodzielnych testów. |
| - | * ''h'(k) = k%m'' | + | </WRAP> |
| - | * ''TAB = NIL, 5, NIL, 9, NIL, 2, 2.5, 1'' | + | |
| + | ==== Zadanie 1 ==== | ||
| + | * W pobranej paczce jest program ''finduniversumsize.cpp'' który służy do wyznaczania wartości //m// na podstawie ilości przechowywanych danych i zakładanej średniej długości listy. | ||
| + | * Jest też moduł ''hchain'' który jest klasą realizującą tablicę haszującą z łańcuchową metodą rozwiązywania konfliktów. | ||
| + | * Zadaniem jest praktyczne przetestowanie tej metody rozwiązywania konfliktów w tablicy o rozmiarze ''3584'' w której zakładamy że średnia długość listy wynosi ''7''. | ||
| + | * Proszę zmodyfikować istniejący program, który: | ||
| + | * tworzy dwie globalne funkcje haszujące typu:<code c++>int f(int val)</code> | ||
| + | * Obie funkcje obliczają indeks w tablicy haszującej przy pomocy działania modulo: <code c++>return val%m</code>gdzie: | ||
| + | * w pierwszej funkcji haszującej ''m = 512 (3584/512 = 7)'', | ||
| + | * wartość //m// w drugiej funkcji wyliczona jest przy pomocy programu ''finduniversumsize''. | ||
| + | * tworzy dwa obiekty klasy ''hash_chain'', których konstruktor przyjmuje następujące wartości: | ||
| + | * W pierwszym obiekcie: | ||
| + | * jako rozmiar tablicy: ''512'', | ||
| + | * wskaźnik do pierwszej funkcji haszującej. | ||
| + | * W drugim obiekcie: | ||
| + | * jako rozmiar tablicy: wartość obliczoną wcześniej przy pomocy programu ''finduniversumsize'', | ||
| + | * wskaźnik do drugiej funkcji haszującej. | ||
| + | * Do każdego obiektu należy wstawić ''3584'' losowych wartości z przedziału ''[0 do np. 10000]''. | ||
| + | * Po wstawieniu należy wyświetlić informacje o stanie tablicy przy pomocy metody: <code c++>hash_chain::printInfo()</code> | ||
| + | * Powyższe dwie czynności można powtórzyć kilkakrotnie obserwując rozmieszczenie elementów w tablicy, oraz średnie odchylenie od średniej. | ||
| + | * Można zauważyć że w takim przypadku obie funkcje haszujące są mniej więcej tak samo dobre (jednak minimalnie lepsze rezultaty daje ta z obliczoną wartością //m//). | ||
| + | * Można także próbować manewrować parametrami i obserwować co się dzieje. | ||
| + | * 8-) Kolejnym krokiem zadania jest wygenerowanie pesymistycznego przypadku dla pierwszej funkcji haszującej: po wylosowaniu wartości przesuwamy jej bity o np. ''2'' w lewo i ustawiamy najmniej znaczący | ||
| + | * Obserwujemy co się dzieje. W obiekcie pierwszym rozmieszczenie wartości jest dużo mniej równomierne -> wzrasta średnie odchylenie. | ||
| + | * Można było się tego spodziewać ponieważ reszta z dzielenia przez wartość będącą ''p''-tą potęgą ''2'' to nic innego jak p najmniej znaczących bitów liczby. Zatem wszystkie generowane indeksy mają takie same wartości dwóch ostatnich bitów. | ||
| + | * Proszę analogicznie przesunąć i dowolnie ustawić ''4'' bity -> wynik: jeszcze gorsza jakość. | ||
| + | * 8-) Dla drugiej funkcji haszującej też bez problemu można wyznaczyć zestaw danych pesymistycznych -> JAK? Proszę dopisać operację "psującą" dane dla drugiej funkcji. | ||
| + | * 8-) Proszę "zepsuć" dane dla pierwszej i drugiej funkcji jednocześnie. Jak teraz poprawić rozłożenie danych w tablicy haszującej? | ||
| + | |||
| + | ==== Zadanie 2 ==== | ||
| + | 8-) W paczce znajdują się pliki ''hopen.cpp'' i ''hopen.h'' które zawierają definicję klasy realizującej tablicę haszującą w której konflikty są rozwiązywane metodą adresowania otwartego. | ||
| + | W tej klasie brakuje obsługi wartości usuniętych. Zadanie polega na uzupełnieniu podanej klasy o obsługę tych wartości. | ||
| + | \\ Rozwiązanie jest krótkie: należy: | ||
| + | - W pliku nagłówkowym dopisać definicję nowej wartości np.<code c++>#define STS_DLTD 2</code> | ||
| + | - W pliku ''cpp'' uzupełnić: | ||
| + | - Metodę ''insert'' | ||
| + | - Metodę ''remove'' | ||
| + | - Ewentualnie w metodzie wypisującej wartości ''printValues'' dopisać jeden warunek:<code c++>else if(_ststab[i] == STS_DLTD) | ||
| + | cout << "DLTD, ";</code> | ||
| - | **Zadanie 4** \\ | ||
| - | Dane jest uniwersum możliwych kluczy: ''U = {2,3,4,5,6,7,8}''. Zaproponuj funkcję ''k(x)'' wyliczającą klucz na podstawie wartości elementu, której przeciwdziedziną jest zbiór ''Y=U''. Następnie wyznacz uniwersalną klasę funkcji haszujących. Dla wybranej funkcji należącej do wyznaczonej rodziny oblicz jej wartości dla każdego klucza należącego do uniwersum. Zakładamy że wartościami elementów mogą być tylko liczby naturalne oraz że rozmiar tablicy haszującej wynosi ''m=8''.\\ | ||
| - | **Przykładowe rozwiązanie** | ||
| - | * ''k(x) = (x%7)+2'' | ||
| - | * ''p = 11'' | ||
| - | * ''Zp = {0,1,...,10}'' | ||
| - | * ''Z*p = {1,2,...,10}'' | ||
| - | * Wybieramy np. ''a=3'', ''b=1''. | ||
| - | * ''h(k)=[(3*k+1)%11]%8'' | ||
| - | **Zadanie 5** \\ | ||
| - | Tablica ''TAB'' jest tablicą haszującą o rozmiarze ''m=12'' w której konflikty są rozwiązywane metodą łańcuchową. Funkcja haszująca jest modularną funkcją haszującą. Zakładając że indeksowanie tablicy rozpoczyna się od ''1'' oraz że funkcja obliczająca klucz ma postać ''k(x)=2x+4'' podaj przynajmniej ''5'' różnych wartości elementów, które mogą być zapisane w tablicy pod indeksem ''7''. \\ | ||
| - | **Rozwiązanie** \\ | ||
| - | * ''h(k) = (k%12)+1'' | ||
| - | * ''(k%12)+1 = 7'' | ||
| - | * ''k%12 = 6 ⇒ k = 12i+6'', gdzie ''i={0,1,...}'' | ||
| - | * ''12i+6 = 2x+4'' | ||
| - | * ''12i+2 = 2x'' | ||
| - | * ''6i+1 = x'', gdzie ''i={0,1,...}'' | ||
| - | * Co nam generuje ciąg wartości których docelowy indeks to ''7''. | ||
| - | **Zadanie 6** \\ | ||
| - | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą metody łańcuchowej. Haszowanie jest wykonywane przez mnożenie dla ''A=0.4''. Zakładamy że tablica ma rozmiar ''m=8'' i jest początkowo pusta. Funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x)=x+8''. Napisz wzór funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''3, 1, 7, 11, 4''. \\ | ||
| - | **Rozwiązanie** \\ | ||
| - | * Po przetworzeniu powyższych wartości przez funkcję ''k(x)'', powstaje następujący zbiór kluczy \\ ''k = {11,9,15,19,12}'' | ||
| - | * ''h(k) = floor(8*(0.4k%1))'' | ||
| - | * ''TAB = [7], NIL, NIL, [3], [1, 11], NIL, [4], NIL'' | ||
