Rychlé šípy (Mirek Dušín, Jarka Metelka, Jindra Hojer, Červenáček a Rychlonožka) si založili internetový časopis TAM-TAM. Protože zpráv je mnoho a všichni potřebují všechno vědět, rozhodli se evidovat zprávy publikované v TAM-TAMu a jejich přečtení jednotlivými členy pomocí hašovacích tabulek.

Jednotlivé zprávy jsou věty, každá je zapsaná na jednom řádku. Jejich délka nepřesáhne 50 znaků. Text správ neobsahuje interpunkci (tečky, čárky, otazníky apod.). Text zpráv sestává pouze ze znaků malé anglické abecedy. Zprávy publikované v TAM-TAMu se mohou vyskytovat i opakovaně a je nutné evidovat aktuální počet opakování zprávy.

Členové Rychlých šípů jsou v programu označováni křestními jmény bez diakritiky a stanoveným pořadím (od 1 do 5):

1. Mirek
2. Jarka
3. Jindra
4. Rychlonozka
5. Cervenacek

Hašovací tabulka – každý z členů Rychlých šípů má přístup do vlastní hašovací tabulky. Hašovací funkce pro řetězce je definována standardně (řetězec s):

$\mathop{\text{hash}}(s) = \left(s[0] + s[1] * p + s[2] * p^2 + ... + s[n-1] * p^{n - 1}\right) \bmod m= \left({\sum_{i=0}^{n-1} s[i] * p^{i}}\right) \bmod m = \left({\sum_{i=0}^{n-1} s[i] * p^{i} \bmod m}\right)$

kde $ p = 32 $,

$ s[i] $ je kód $i$-tého znaku řetězce, a má kód 1, b → 2, c → 3, …, z → 26, (mezera) → 31,

$m$ – velikost tabulky. Velikost tabulky si každý z členů Rychlých šípů volí na začátku výběrem oblíbeného prvočísla nebo je její hodnota nastavena na 11. Pokud faktor naplnění dosáhne hodnotu 70%, velikost tabulky se zdvojnásobí. Pokud naopak faktor naplnění klesne při mazání zpráv pod 30%, velikost tabulky se zmenší na polovinu, nikdy ale neklesne pod počáteční velikost.

Výsledek hašovací funkce pro vybrané řetězce při velikosti tabulky $m=11$: aa → 0, ab → 10, abc → 2, aab → 2, adb → 10, carodej → 3.

Program zpracovává zprávy a direktivy ze standardního vstupu. Direktivy jsou umístěny na samostatných řádcích a jsou označeny znakem #.

Pokud si členové Rychlých šípů volí prvočísla pro počáteční velikost hašovací tabulky, je na prvním řádku direktiva #i následována jednotlivými prvočísly – jedno až pět prvočísel, které odpovídají stanovenému pořadí členů.

• #i 13 7 – Mirek volí prvočíslo 13, Jarka 7 a ostatní členové mají 11
• #i 7 11 13 17 19 – Mirek volí prvočíslo 7, Jarka 11, Jindra 13, Cervenacek 17 a Rychlonozka 19
• Pokud direktiva #i chybí, všichni členové volí prvočíslo 11.

Direktiva #a – do hašovacích tabulek všech členů se přidají zprávy na následujících řádcích.

Direktiva #cis – přepne člena s číslem cis podle stanoveného pořadí. Pro daného člena je dále možné provádět následující operace:

• #p – vypíše základní informace o členovi Rychlých šípů – jméno, aktuální velikost tabulky a aktuální počet unikátních zpráv (bez opakování) v tabulce (viz příklad 3)

Pokud následují další zprávy, pak se pro každou zprávu vypíše text zprávy, její aktuální pozice (index) v tabulce a aktuální počet opakování zprávy (viz příklad 11 a 12). Pokud se zpráva v tabulce nenachází, její aktuální index je -1 a počet opakování 0.

• #d – člen Rychlých šípů si zprávy následující na dalších řádcích přečte, zprávy jsou z tabulky člena vymazány. Zprávy jsou vždy mazány jednotlivě.

Při řešení je potřeba striktně dodržovat pravidla pro tvorbu hašovacích tabulek. Nejprve doporučujeme řádně otestovat hašovací funkce. Vstupní řetězce jsou dlouhé a při výpočtu je potřeba se vypořádat s velkými hodnotami hašovacích klíčů a jejich možným přetečením. Při výpočtu hašovací funkce pro daný řetězec počítáme pouze znaky anglické abecedy a mezery, ostatní znaky ignorujeme.

První sada testů testuje správné čtení prvního řádku a nastavení správné velikosti hašovacích tabulek pro všechny členy Rychlých šípů. Současně je potřeba implementovat možnost jednoduchého zadávání zpráv do tabulek – bez nutnosti změny velikosti tabulky. Faktor naplnění nepřekročí 70%. U každé zprávy evidujeme, kolikrát je aktuálně v tabulce pro daného člena zapsaná.

V další fázi je potřeba odladit vkládání zpráv do tabulek s možností změny velikosti tabulky při jejím naplnění. Při kolizích při vkládání zpráv využívejte metodu lineárního hledání nejbližšího volného místa (linear probing). V této fázi řešení se může objevit problém nesprávně implementované funkce $\mathop{\text{hash}}$. Doporučujeme vše řádně zkontrolovat podle příkladů 11 a 12.

Následně je potřeba implementovat možnost vymazat zprávy. Aby lineární hledání místa (linear probing) fungovalo, je nutné uvolněná místa označit speciálními znaky a ty odstranit až při změně velikosti tabulky. Zde je nutné zamyšlení, k čemu takto speciálně označovaná místa slouží. Je dobré si promyslet, že je lze využít ke vkládání nových zpráv do tabulky, jsou však “přeskakována” při vyhledávání zpráv. Změnu velikosti tabulky při mazání provádíme, pokud faktor naplnění klesne pod 30%.

Pokud všechny testy řádně proběhnou, je poslední část práce věnována časové a prostorové optimalizaci. Preferujeme využití dynamické paměti.

#a
sel deda s babickou na hriby
v lesiku se mu vsak nelibi
mravenci kousou ho komari stipou
veverky za krk mu jehlici sypou
pojd babi radeji na ryby
#1
#p
#2
#p
#3
#p
#4
#p
#5
#p

Mirek
	11 5
Jarka
	11 5
Jindra
	11 5
Rychlonozka
	11 5
Cervenacek
	11 5

00000000: 4d 69 72 65 6b 0a 09 31  Mirek..1
00000008: 31 20 35 0a 4a 61 72 6b  1 5.Jark
00000010: 61 0a 09 31 31 20 35 0a  a..11 5.
00000018: 4a 69 6e 64 72 61 0a 09  Jindra..
00000020: 31 31 20 35 0a 52 79 63  11 5.Ryc
00000028: 68 6c 6f 6e 6f 7a 6b 61  hlonozka
00000030: 0a 09 31 31 20 35 0a 43  ..11 5.C
00000038: 65 72 76 65 6e 61 63 65  ervenace
00000040: 6b 0a 09 31 31 20 35 0a  k..11 5.

Pro upřesnění uvádíme i hexadecimální výpis výsledku. Hodnota 0a odpovídá konci řádku, hodnota 09 je tabulátor.

sel deda s babickou na hriby
v lesiku se mu vsak nelibi
#a
mravenci kousou ho komari stipou
veverky za krk mu jehlici sypou
pojd babi radeji na ryby
#p

Error: Chybny vstup!

Chybný vstup nastává tehdy, když není známo, pro kterého člena Rychlých šípů se má informace vypsat (direktiva #p).

#p
sel deda s babickou na hriby
v lesiku se mu vsak nelibi
#a
mravenci kousou ho komari stipou
veverky za krk mu jehlici sypou
pojd babi radeji na ryby
#5
#p

Cervenacek
	11 3

Error: Chybny vstup!

Na začátku není známo číslo člena Rychlých šípů, proto se nevypíše žádná informace, program eviduje chybný vstup (direktiva #p na začátku).

Testuje změnu velikosti hašovací tabulky při překročení faktoru naplnění.

Testuje vkládání zpráv do tabulek jednotlivých členů Rychlých šípů.

Náhodné testy vkládání zpráv do tabulek na delším textu.

Testuje mazání zpráv z tabulek jednotlivých členů Rychlých šípů. Následují náhodné testy.

Další testy kontrolují rychlost výpočtu a paměťovou náročnost běhu programu. Test delete_09 je stejný jako testy následující, pokaždé se generuje jiná úloha. Pokud neumíte chybu najít, je velká pravděpodobnost, že při opakované žádosti o hodnocení narazíte na úlohu, v níž se chyba v programu ve výpisu testu objeví.

Ryšánek Jiří: Dětské básničky. Dostupné na: https://www.detskebasnicky.cz/

Foglar Jaroslav: Záhada hlavolamu.

Goethe, Johann Wolfgang: Faust.

Úvodní obrázek Rychlých šípů. Dostupné na: https://magazin.aktualne.cz/rychlym-sipum-je-80-let-komiks-se-stal-legendou/r~4de859f2fdef11e8b9390cc47ab5f122/

Veřejné testovací soubory - DSA_HW03.

clang -Wall -Werror -pedantic -std=c99
clang -Wall -Werror -pedantic -std=c+ +17

javac *.java
java -classpath Hash

hašování
lineární zkoušení (linear probing)
otevřené adresování (open addresing)