Search
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ány křestními jmény bez diakritiky a stanoveným pořadím (od 1 do 5):
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):
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,
a
b
c
z
$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.
aa
ab
abc
aab
adb
carodej
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
#i
#i 13 7
#i 7 11 13 17 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.
#a
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:
#cis
cis
#p
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
Error: Chybny vstup!
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.
HashSet
HashMap
10000
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
#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
#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
#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 #6 #p
Error: Chybny vstup! Error: Chybny vstup!
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
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
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).
#i 11 7 13 17 19 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 #1 #p #2 #p #3 #p #4 #p #5 #p
Mirek 11 3 Jarka 7 3 Jindra 13 3 Rychlonozka 17 3 Cervenacek 19 3
#i 11 7 13 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 #1 #p #2 #p #3 #p #4 #p #5 #p
Mirek 11 3 Jarka 7 3 Jindra 13 3 Rychlonozka 11 3 Cervenacek 11 3
Testuje změnu velikosti hašovací tabulky při překročení faktoru naplnění.
Mirek 11 3 postavili skolu 8 1 na severnim polu 7 1 Mirek 22 9 postavili skolu 8 2 na severnim polu 18 1 Mirek 22 11 postavili skolu 8 2 na severnim polu 18 2 Mirek 44 16 s 20 1 ss 11 1 sss 21 1 ssss 12 1 sssss 19 1
Mirek 22 9 postavili skolu 8 1 na severnim polu 18 1 Jarka 13 9 postavili skolu 12 2 na severnim polu 7 1 Jarka 26 11 postavili skolu 12 2 na severnim polu 6 2
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.
Mirek 22 13 koza v plavkach 7 1 koza roza v globusu 15 1 Mirek 22 11 koza v plavkach -1 0 koza roza v globusu -1 0 chce nastoupit do busu 3 1 Mirek 22 13 koza v plavkach 7 1 koza roza v globusu 15 1
Mirek 22 13 koza v plavkach 7 1 koza roza v globusu 15 1 Mirek 22 11 koza v plavkach -1 0 koza roza v globusu -1 0 chce nastoupit do busu 3 1 Mirek 44 17 koza v plavkach -1 0 koza roza v globusu -1 0 Jarka 52 19 koza v plavkach 44 1 koza roza v globusu 45 1 Jindra 34 19 koza v plavkach 9 1 koza roza v globusu 15 1
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í.
delete_09
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/
Java
Python
C/C++
Veřejné testovací soubory - DSA_HW03.
hash.py
Hash.java
hash.c
hash.cpp
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)
20