Datové struktury I - 5. úkol

Termín odevzdání: 1. ledna 2017.
Způsob odevzdání: Odevzdáním na stránce https://kam.mff.cuni.cz/~ds1/.
Obecná pravidla: Prečtěte si je důkladně

Popis problému

Implementujte dvě hašovací tabulky (lineární přidávání a kukačka) a tři systémy hašovacích funkcích (tabulační, multiply-shift a naivní modulo). Poté studujte jejich chování ve dvou testovacích případech.

Systémy funkcí

Nechť U = {0, ..., 2^u - 1} je univerzum a m=2^k je velikost hašovací tabulky, kde u je alespoň 31. Popsané systémy funkcí hašují univerzum U do tabulky {0, ..., m - 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í (kromě jedné, pokud použijete 31 nebo 63-bitová čísla místo 32 nebo 64-bitových), t.j. x = x₁x₂...x_c. Pro každou z těchto c částí uniformně náhodně inicializujme její tabulku, která obsahuje 2^u/c bitových řetězců délky k. Pak h(x) = T₁(x₁) ⊕ T₂(x₂) ⊕ ... ⊕ T_c(x_c). 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 takto získaných hodnot. Použijte vhodnou hodnotu parametru c, která balancuje dobu vypočtu hešovací funkce a množství paměti nutné k uložení všech tabulek.

Multiplikativní funkce. Nechť x je prvek z univerza U, a nechť a ∈ U je uniformně náhodně zvolené liché číslo. Pak h(x) = ((a * x) mod |U|) / (|U| / m). Implementujte tuto funkci efektivně.

Naivní modulo. Nechť x ∈ U. Pak h(x) = x mod m.

Náhodný testovací případ

Studujte, jak doba běhu a počet kroků závisí na faktoru zaplnění pro následující kombinace hešovacích tabulek a funkcí.

Kukaččí tabulka a tabulková hešovací funkce
Kukaččí tabulka a hešovací systém multiply-shift
Lineární přidávání a tabulková hešovací funkce
Lineární přidávání a hešovací systém multiply-shift
Lineární přidávání a naivní modulo

Studujeme pouze složitost (průměrná doba běhu a průměrný počet kroků) operace Insert. V lineárním přidávání je počet kroků definován jako počet přihrádek, ke kterým je nutné přistoupit než se najde prázdná přihrádka. V kukaččí tabulce je počet kroků definován jako počet prohození prvků (zavolání swap) než se podaří prvek vložit, a to včetně prohazování způsobených přebudováním tabulky (operace rehash).

Pro tento test nakreslete dva grafy takové, že oba obsahují jednu křivku pro každou kombinaci hešovací funkce a tabulky. První graf má ukazovat, jak průměrná čas jedné operace Insert závisí na faktoru zaplnění, a druhý graf má ukazovat, jak průměrný počet kroků jedné operace Insert závisí na faktoru zaplnění. V tomto testu uvažujte tabulku pevné velikosti, která je alespoň m = 2²⁰, a použijte náhodný generátor čísel k vygenerování vstupní posloupnosti vkládaných prvků.

Při vložení prvku má tabulka nějaký faktor zaplnění. Protože cílem je studovat závislost složitosti operace Insert na faktoru zaplnění, složitost operace Insert průměrujte přes vkládání prvků do podobně zaplněné tabulky. Například můžete rozdělit posloupnost operací Insert na 100 podposloupností a změřte průměrnou složitost každé podposloupnosti.

Jako obvykle je cílem nakreslit graf, ze kterého bude zřejmé chování zadané datové struktury. Proto můžete jednotlivé křivky ukončit v okamžiku, kdy naměřené hodnoty jsou příliš velké. Tabulku s lineárním přidáváním je sice teoreticky možné úplně naplnit, ale experiment můžete ukončit, když faktor zaplnění je skoro 1. Přidávání prvků do kukaččí tabulky můžete ukončit, když vložení jednoho prvku způsobí příliš mnoho přebudování (volání rehash).

Testovací případ se sekvenční vkládáním do tabulky s lineárním přidáváním

V tomto testu uvažujeme pouze lineární přidávání a tabulkovou a multiply-shift hešovací funkci a měříme pouze průměrný počet kroků operace Insert. Posloupnost vkládaných prvků je 1, 2, 3, ... . Cílem je studovat závislost počtu kroků na velikosti tabulky m, když je tabulka skoro zaplněná (faktor zaplnění je zhruba 0.9). Velikosti tabulek jsou vždy mocninou dvojky. Měření dostatečně krát opakujte pro každou velikost m. V každém měření nejprve vložte prvky menší než 0.89 m a poté změřte průměrný počet kroků S_t na vložení jednoho prvku od 0.89 m do 0.91 m. Nakonec spočtěte následujících pět statistických hodnot pro každou velikost m k získání pěti křivek pro tabulkové i multiply-shift hešování.

Nejmenší hodnotu S_t přes všechny testy t,
největší hodnotu S_t,
průměrnou hodnotu S_t,
medián S_t a
poslení decil z S_t, tj. číslo větší než 90% hodnot S_t ale menší než 10% hodnot S_t.

Najděte pěkný způsob zobrazení všech deseti křivek v jednom nebo více grafech. Proveďte dostatečný počet měření tak, aby získané výsledky byly statisticky dostatečně přesné a zvolte vhodný rozsah velikostí tabulek m.

K spočtení požadovaných statistických hodnot z naměřených hodnot můžete použít libovolný vhodný nástroj nebo knihovnu.