Datové struktury 1 - NTIN066 - ZS 2014/2015
5. úkol
Termín odevzdání: Dva dny před zkouškou.
Způsob odevzdání: Odesláním v příloze emailem na ds1@kam.mff.cuni.cz.
Pravidla
- Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší "inspirace".
- Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí "inspirací". Výjimku tvoří odevzdání kódu.
- Úkol a možné postupy řešení můžete probírat s ostatními, avšak respektuje výše uvedené o nesdílení kódu.
- Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.
Popis problému
Naimplementujte kukačkové hašování. Napište program, který přečte ze vstupu testovací data a vloží je do hašovací tabulky velikosti přesně 10 000.
Vstupní data jsou rozdělená na běhy, každý běh sestává z 2 000-8 000 operací Insert 31-bitového čísla, některé prvky můžou být vkládány několikrát.
Řádky Insert začínají písmenem I, poslední řádek běhu obsahuje písmeno R. Za posledním během je řádek s písmenem X.
Po každém běhu se tabulka vyprázdní. Pro každý běh vypište počet operací prohození prvků v tabulce provedených během vkládání vydělený
počtem různých vložených prvků. Započítejte prohazování i během přehašování. Pokud dojde k více než patnácti přehašováním během jednoho běhu, vypište nulu.
Pomocí unixového programu /afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl5-gen-data dostupného v laboratoři Rotunda vygenerujte zkušební data, spusťte na nich
své programy a naměřené hodnoty zaneste do grafu, kde na ose x bude vynesen počet různých vkládaných prvků a na ose y bude vynesen průměrný počet prohození.
Pro posloupnost s 5 000 operacemi Insert vytvořte též graf rozložení doby na jednu operaci Insert, tedy pro dané x mezi 0-50 vyneste na ose y, kolik operací Insert
potřebovalo x prohození. Operace Insert s více než 50 prohozeními započítejte jako x=51. Osu y udělejte v logaritmickém měřítku.
Hašovací funkce: Obě hašovací funkce zvolte jako h_i(x) = (((x * r_i) >> 16) & 0xFFFF) mod 10000, kde r_i je náhodně zvolené 30-bitové číslo.
Při přehašování vyberte další náhodná čísla, čímž dostanete nové hašovací funkce.
Příklad vstupu
I 0
I 1
I 3454050
I 15
R
I 1222
I 0
I 1222
I 1
R
X
Náčrty možných grafů
Generování zkušebních dat
$/afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl5-gen-data XX
vygeneruje data pro měření, kde XX jsou poslední
dvě číslice z vašeho studentského čísla.
Velikost běhu začíná na 2 000 vložených prvcích a roste po 100 až do 8 000 prvků. Příklad spuštění:
pbl5-gen-data 72 | moje-kukacka