Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/05/02 19:14] ikaf |
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/05/11 16:25] ikaf zad2hash |
||
|---|---|---|---|
| Linia 25: | Linia 25: | ||
| 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> | ||
