Cvičení z datových struktur 1 (zimní sem. 21/22)

Cvičení 8. 12. 2021: Hešování za ideálních podmínek

\( \def\H{\mathcal{H}} \def\U{\mathcal{U}} \def\B{\mathcal{B}} \def\O{\mathcal{O}} \)

Nový úkol: není

Staronový úkol: hash_experiment

Nastudujte si "Claim (basic properties of linear probing)" ze skript (strana 13, sekce 6.3), neb se na přednášce nestihl.
Z téže skript si preventivně nastudujte systém Multiply-shift (strany 7,8, sekce 6.1). Sice se na přednášce nějak prošel, ale nejsem si úplně jistý, jak moc konzistentně s tím, co je v úkolu (na rozdíl od skript).
Vůbec, prostě si radši teorii k úkolu projděte ze skript -- mělo by to být plus mínus konzistentní s přednáškou, ale kdo ví.

Řešení cuckoo_hash

Znovu si pořádněte přečtěte informace, které jsem říkal při zadávání. Drtivá většina vašich chyb je tam předem popsaná.
Obecně (tohle se nebodovalo): Hešování je o nedostatku prostoru. V málo prostoru chcete efektivně reprezentovat množinu. Pokud máte prostoru hodně, nejjednodušší řešení, jak se vyhnout kolizím, je prostě pořídit si větší tabulku. Například jeden z důvodů, proč zvolit lineární přidávání, které může mít kvůli srůstání ošklivé vlastnosti, oproti separovaným řetězcům, které se i při hodně kolizích chová relativně pěkně, je prostě to, že separované řetězce spálí spoustu místa na pointerech.
Tj., veškeré operace nad tabulkou by měly pracovat v minimálním prostoru navíc. Například implementace insertu rekurzivně, když to jde snadno smyčkou, je šílené plýtvání místem (obecně je dobré se v takových případech rekurzi vyhýbat). Stejně tak, když si při reheši zkopírujete celou tabulku, nebo dokonce, když máte reheš rekurzivní, takže ve finále můžete skončit s několika kopiemi tabulky!

Notace:

\(\U\) : univerzum
\(U = |\U|\)
\(S \subset \U\) : množina, kterou hešujeme
\(n = |S| \)
\(\B\) : kyblíčky/políčka v hešovací tabulce
\(m = |\B|\)
\(h, h_1, h_2, \dots\) : všelijaké hešovací fce

Na cvičení budeme používat definice univerzality a nezávislosti dle skript, stejně se z nich nejspíš budete učit na zkoušku. Bohužel, v téhle oblasti je terminologie silně zmatená a neustálená.
Rozdíly terminologie mezi přednáškou a skripty:

univerzální v přednášce = 1-univerzální ve skriptech
obecná c-univerzalita se na přednášce nedefinovala, případně jen neformálně jako (c-)přibližná univerzalita
(pozor, některá literatura 2-univerzalitou myslí 2-nezávislost, viz níže)
k-nezávislost v přednášce = (k,1)-nezávislost ze skript
ekvivalent skriptové k-nezávislosti je v rámci přednášky přibližná k-nezávislost, ale nedefinováno formálně
obecná (k,c)-nezávislost ze skript je stejný případ jako výše a univerzalita

Př. 1: Modulo ničí univerzalitu

Ukažte, že pokud máme univerzální systém hešovacích funkcí \(\H\), pak systém \(\H'\), kde ke každé fci navíc přidáme modulo m, už nemusí být univerzální.
Trochu formálněji: Dokažte, že pro každé \(c\) a \(m > 1\) existuje univerzum \(\U\) a systém \(\H\) z \(\U\) do \(\U\) tak, že \(\H\) je univerzální, ale \(\H'\) už není c-univerzální.
Hint: Můžou se hodit systémy z minulého cvika.

Př 2.: Rabin-Karp

Odbočka k textovým algoritmům.
Máme dva řetězce, dlouhé seno S a krátkou jehlu J a chceme najít v senu najít všechny výskyty jehly. Označíme si délky \(|S| = n\) a \(|J| = k\).
Triviální algoritmus v čase \(\O(nk)\) prostě zkontroluje každý podřetězec sena délky k znak po znaku, zda to není jehla. Vylepšete triviální algoritmus pomocí hešování tak, abyste dostali v průměru složitost \(\O(n + k + kt)\), kde t je počet výskytů jehly v seně.
Může pomoct si vzpomenout na ADS2. Taktéž se bude hodit vzpomenout si, jak se dají efektivně hešovat řetězce, viz například skripta (pro změnu), konec sekce 6.1.