Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:asd:cwiczenia:2012-hashing [2012/05/11 16:22] ikaf zad1 |
pl:dydaktyka:asd:cwiczenia:2012-hashing [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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? | ||
| - | |||
| - | |||
| - | |||
