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

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

m > 1

existuje univerzum

U

a systém

H

U

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

| J | = k

.
Triviální algoritmus v čase

O (n k)

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 + k t)

, 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.