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

Řešení matrix_transpose a poznámky k experimentu

• Vzorák se opět objeví v ReCodExu. Pokud ho tam nenajdete, napište.
• Experiment má i bonusovou část měření na reálném HW.
  • Jen v C++, můžete použít vzorák (zmiňte to).
  • Dávejte pozor, že vám měření ovliňují ostatní spuštěné programy.
  • Nebo třeba zkompilování programu v debug módu.

Řešení ab_experiment

Nový úkol: cuckoo_hash

• Jeden z nejkomplikovanějších úkolů
• Ujistěte se nejdřív, že kukačkovému hešování rozumíte. Viz např. skripta, kapitola 6.2.
• Insert má běžet v \( \mathcal{O}(1)\) průměrně amortizovaně. Nemůžete si tedy dovolit vždy, nezávisle na náhodě, v insertu počítat něco, co trvá déle. Například logaritmus.
• Při detekci cyklu si nemůžete jen tak bez analýzy změnit limit, po kterém se spustí reheš. A to ani jedním směrem! Zvýšením limitu sice nepoškodíte korektnost, ale můžete rozbít složitost. Pointa analýzy je, že chození po cyklu sice může trvat déle než konstantu, ale pravděpodobnost, že budu po cyklu chodit dlouho je dost malá na to, by se čas "zprůměroval" na konstantu. Když zvýšíte limit, tak zvyšujete čas strávený chozením po cyklu, ale nesnižujte pravděpodobnost.
• Tak či tak, můžete brát jako fakt, že i limit \(6\log m\) funguje, přičemž \(m\) je velikost tabulky.
• Dejte si pozor na "triviální" dvojcykly. Při vyhazování a následném znovuzahešování prvku je třeba pečlivě vybrat, jakou funkci pro znovuzahešování použijeme, abysme prvek nezahešovali do místa, ze kterého byl právě vyhozen. To může totiž vytvořit dvojcyklus, kterému se dá vyhnout a u kterého analýza i počítá s tím, že se mu vyhneme. Velice doporučuji si zkusit pár kroků vyhazování udělat, se všemi možnými variantami, která funkce zahešovala co kam.

Setting dnešního cvičení

• Pořádně sepsané v materiálech k Tungově paralelce, osmé cvičení. Včetně řešení příkladů a mnoha dalšího (pozor na spoilery!). V poznámkách můžou být ještě tu a tam chyby, které Tung postupně opravuje, je tedy lepší si poznámky nestahovat a podívat se na aktuální na webu.
• Řešíme klasický slovníkový problém hešováním: Máme obrovské univerzum, v něm maličkou (vůči univerzu) podmnožinu a chceme jí skrz nějakou hešovací fci namapovat do rozumně velké tabulky
• Hešovací fce z principu není prostá \( \Rightarrow \) můžou nastat kolize.
• Věškerou náhodu uvažujeme přes volbu hešovací funkce, hešované prvky jsou fixní (ale neznámé).
• Dnes uvažujeme úplně náhodnou hešovací funkci, tj. rovnoměrně náhodně vybranou ze všech možných fcí z univerza do kyblíčků.
• Pro takovou fci \(h\) platí \( \Pr[h(x) = a] = 1/m\) pro libovolné \(x, a\) a navíc zahešování více prvků je vždy úplně nezávislé.

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

Př. 1: Kvadratická tabulka

1. Nejdřív spočtěte pravděpodobnost, že dva konkrétní prvky při hešování zkolidují.
2. Pak už stačí jen správně použít union-bound, tedy nerovnost \(\Pr[A\vee B] \le \Pr[A]+\Pr[B]\).

Př. 2: Narozeninový paradox

1. Přesně spočtěte pravděpodobnost, že při vložení \(k\) prvků nedojde ke kolizi (\(p_k\). Může se hodit indukce.
2. Vytvořte vhodný odhad \(p_k\) pomocí nerovnosti \(1+x \le e^x\), která platí pro všechna reálná \(x\)
3. Spokojeně skliďte plody své práce zvolením vhodného \(k\).