Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/05/02 19:12] ikaf |
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/05/11 16:25] ikaf zad2hash |
Termin zajęć: 8./9. maja 2012 | 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 |
* Metoda adresowania otwartego | * Metoda adresowania otwartego |
| |
===== Download ===== | ===== Do pobrania: ===== |
Proszę pobrać archiwum {{:pl:dydaktyka:asd:cwiczenia:hashing.zip|}}, w którym znajdują się pliki potrzebne do wykonania ćwiczeń na zajęciach. | Proszę pobrać archiwum {{:pl:dydaktyka:asd:cwiczenia:hashing.zip|}}, w którym znajdują się pliki potrzebne do wykonania ćwiczeń na zajęciach. |
| |
| |
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). | 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). |
| |
| ===== Ćwiczenia i zadania implementacyjne ===== |
| <WRAP center round info 60%> |
| Punkty oznaczone 8-) należy samodzielnie wykonać w domu, pozostałe punkty stanowią opis, wprowadzenie, zachętę do samodzielnych testów. |
| </WRAP> |
| |
| ==== 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> |
| |
| |
| |