|
|
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/05/11 16:22] ikaf zad1 |
pl:dydaktyka:asd:cwiczenia:2012-hashing [2019/06/27 15:50] |
====== Tablice haszujące ====== | |
| |
Termin zajęć: 8./9. maja 2012 | |
| |
===== Do przygotowania - teoria na temat: ===== | |
- Rodzaje haszowania | |
* haszowanie bezpośrednie | |
* haszowanie modularne | |
* haszowanie przez mnożenie | |
* haszowanie uniwersalne | |
- Problem konfliktów podczas haszowania | |
- Sposoby rozwiązywania konfliktów | |
* Metoda łańcuchowa | |
* Metoda adresowania otwartego | |
| |
===== Do pobrania: ===== | |
Proszę pobrać archiwum {{:pl:dydaktyka:asd:cwiczenia:hashing.zip|}}, w którym znajdują się pliki potrzebne do wykonania ćwiczeń na zajęciach. | |
| |
Oto krótki opis plików: | |
* ''finduniversumsize.cpp'' - program obliczający optymalną wielkość tablicy haszującej na podstawie przewidywanej ilości danych i średniej długości łańcucha. | |
* ''findnextprime.cpp'' - program wyszukujący kolejną liczbę pierwszą. | |
* ''hchain.h'' + ''hchain.cpp'' - moduł zawierający klasę implementującą tablicę haszującą z łańcuchową metodą rozwiązywania konfliktów. | |
* ''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ń. | |
* ''mainmodular.cpp'' - niezobowiązujący plik pokazujący przykładowe wykorzystanie klas. | |
| |
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? | |
| |
| |
| |
| |