Datové struktury I - NTIN066 - ZS 2015/2016 - 5. úkol

Termín odevzdání: 19. leden 2016.
Způsob odevzdání: Odesláním v příloze emailem na ds1@kam.mff.cuni.cz.

Pravidla

Popis problému

Implementujte dvě hašovací tabulky a dva systémy hašovacích funkcích. Následně je srovnejte na dvou variantách operací složených z vložení a vyhledávání. Operace Insert vytváří množinu, tedy Insert s duplicitním klíčem nezmění tabulku, jen se započítá do statistik. První varianta operací, Insert, je zvolena tak, že vyhledávání tvoří 20 % operací. Druhá varianta, Find, tak, že vyhledání tvoří 80 % operací.

Implementujte lineární přidávávaní (linear probing) dle prědnášky. Implementujte variantu kukaččího hašování z přednášky s jedinou tabulkou. Velikost tabulky zvolte rovnou parametru M, který je popsán v sekci o generování dat. Pro generovaní dat pro kukačkové hašování použijte parametr C, který omezí faktor naplnění.

Systémy funkcí

Nechť U = {0, ..., 2u - 1} je univerzum a m=2k je velikost hašovací tabulky. Popsané systémy funkcí hašují univerzum U do prostoru {0, ..., m - 1}. Pro účely zadaní použijte jako univerzum množinu {0, ..., 232 - 1}. Generátor dat generuje hodnoty z množiny {0, ..., 231 - 1}.

Tabulační funkce. Nechť x je prvek univerza U, představme si jej jako bitový řetězec rozdělený na c stejně dlouhých částí, t.j. x = x1x2...xc. Pro každou z těchto c částí uniformně náhodně inicializujme její tabulku, která obsahuje 2u/c bitových řetězců délky k. Pak h(x) = T1(x1) ⊕ T2(x2) ⊕ ... ⊕ Tc(xc). Tedy pro každou část získáme index do tabulky, kde je uloženo číslo z množiny {0, ..., m - 1}. Výsledek hašovací funkce je XOR takhle získaných hodnot. Rychlá implementace spoléhá na fixní volbu c, například c = 4.

Multiplikativní funkce. Nechť x je prvek z univerza U, a nechť a ∈ U - {0} je uniformně náhodně zvolené číslo. Pak h(x) = ((a * x) mod |U|) / (|U| / m).. Pro 32-bitové univerzum lze tutu funkci implementovat efektivně pomocí posunů a zanedbání přetečení při násobení.

Výsledek měření

Pro každou variantu dat udělejte dva grafy. První graf bude ukazovat průměrný počet operací na jednu operaci Insert nebo Find vzhledem k faktoru naplnění, druhý graf bude ukazovat průměrný čas (zvolte milisekundy nebo mikrosekundy tak, aby byl graf přehledný) na operaci Insert nebo Find vzhledem k faktoru naplnění.

Linear Probing
Počet operací pro Insert nebo Find je 1 + délka sekvence, kterou bylo nutné projít k nalezení nebo vložení prvku.
Kukačkové hašování
Find potřebuje jednu nebo dvě operace. Insert zkusí nejdřív vyhledat prvek, tohle vyžaduje jednu nebo dvě operace. Když vkládaný prvek není nalezen, pak udělá několik "swap" operací. Také započítejte i operace swap z případných rehash operací. Maximální počet rehashů v jedné operaci Insert nastavte na 15. V případě, že některý Insert tento limit překročí, daný běh do výsledku nezapočítavejte. V případě, že každý běh pro daný faktor naplnění skončí selháním, load factor do grafu nezahrnujte/neho ho zakreslete jako nulu.

Sepište zprávu, v níž bude:

Generování dat

Pro vygenerování testovacích dat použijte už zkompilovaný generátor /afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw5/hashgen dostupný v unixové laboratoři Rotunda. Spusťte ho s následujícími parametry:

Generátor produkuje textový výstup, každý řádek je tvaru:

Na jedno spuštění generátor vytvoří sadu testů s faktorem naplnění od 30 do 90% (nebo 55 %, pokud jste zadali i parameter C). Pro každý faktor naplnění jsou vygenerovány čtyři běhy. Výsledky zakreslete zprůměrovány přes tyto běhy.

Příklad vstupu

# 2 4
I 1
I 2
I 1
I 3
F 1
# 3 4
I 2
I 3
I 7
I 3
I 2
F 2
F 0

Odevzdání

Pošlete e-mail s předmětem tvaru 'HW5-55973318' (t.j. HW5-studentské číslo) s těmito přílohami:

Tělo e-mailu nechť obsahuje údaje podle tohoto vzoru:


Jmeno: Martin Babka
Pseudonym pro vysledky na webu: Babočka Admirál
Cviceni: pondeli-12:20-lichy