======== HW03 Hašování ======== {{:courses:b6b36dsa:ukoly:postavyrs_.png?300 | Rychlé šípy - postavy }} 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): - Mirek - Jarka - Jindra - Rychlonozka - 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. Hašovací funkce je vypočítávána často a opakovaně. Ve snaze o optimální řešení doporučujeme zabývat se jejím optimálním výpočtem. Například jednoduchou úvahou lze omezit časově náročné počítání mocnin. ====== Vstup programu ====== 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**. Velikost tabulky pro jednotlivé členy Rychlých šípů nikdy neklesne pod velikost danou inicializačním prvočíslem! 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 [[courses:b6b36dsa:ukoly:hw03#priklad_3_prelude_03|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 [[courses:b6b36dsa:ukoly:hw03#priklad_11_12_append_03_append_04|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ě. Pokud vstup nelze parsovat podle zadaných pravidel, vypište zprávu o chybě ''Error: Chybny vstup!''. Program by se měl z chyby zotavit a pokračovat ve výpočtu. Jednotlivé zprávy jsou zapsány na řádcích. Za zprávu je považován text mezi prvním (nejlevějším) a posledním (nejpravějším) písmenem anglické abecedy. Mezery na začátku a na konci řádku, stejně jako znak konce řádku nejsou součástí zprávy!!! ====== Algoritmus řešení úlohy ====== 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á. Změnu velikosti tabulky provádíme zpracováním zpráv podle pořadí jejich aktuálního indexu v tabulce. 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 [[courses:b6b36dsa:ukoly:hw03#priklad_11_12_append_03_append_04|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. Varujeme před využitím metod z nejrůznějších knihoven (''HashSet'', ''HashMap'' apod.). Tyto nástroje vám neposkytnou údaje, které jsou v testech kontrolovány, například aktuální indexy prvků. Maximální počet zpráv zapisovaných do tabulek je ''10000''. ====== Kontrolní testy ====== Testovací soubory najdete {{ :courses:b6b36dsa:ukoly:dsa_hw03.zip |zde}}. ===== Nastavení velikosti tabulek a základní vkládání ===== ==== Příklad 1 – prelude_01 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 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 | žádný | žádný | 0 | ==== Příklad 2 – prelude_02 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | #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 | žádný | žádný | 0 | ==== Příklad 3 – prelude_03 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | #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 500000000: 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. | žádný | 0 | 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. ==== Příklad 4 – prelude_04 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | #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 | žádný | Error: Chybny vstup! Error: Chybny vstup! | 0 | ==== Příklad 5 – prelude_05 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 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 | žádný | Error: Chybny vstup! | 0 | Chybný vstup nastává tehdy, když není známo, pro kterého člena Rychlých šípů se má informace vypsat (direktiva ''#p''). ==== Příklad 6 – prelude_06 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | #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! | 0 | 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). ==== Příklad 7 – prelude_07 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | #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 | žádný | 0 | ==== Příklad 8 – prelude_08 ==== ^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | #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 | žádný | 0 | ===== Vkládání při překročení faktoru naplnění ===== ==== Příklad 9, 10 – append_01, append_02 ==== Testuje změnu velikosti hašovací tabulky při překročení faktoru naplnění. ==== Příklad 11, 12 – append_03, append_04 ==== ^ Výstup (stdout) - append_03 ^ Výstup (stdout) - append_04 ^ | 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 | ==== Příklad 13 - 16 – append_05 – append_08 ==== Testuje vkládání zpráv do tabulek jednotlivých členů Rychlých šípů. ==== Příklad 17, 18 ==== Náhodné testy vkládání zpráv do tabulek na delším textu. ===== Mazání dat z tabulek ===== ==== Příklad 19, 20 – delete_01, delete_02 ==== ^ Výstup (stdout) - delete_01 ^ Výstup (stdout) - delete_02 ^ | 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 | ==== Příklad 21 - 26 – delete_03 – delete_08 ==== 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í. ====== Zdroje textů a obrázků ====== 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/]] ====== Odevzdání a hodnocení ====== Úlohu je možné řešit v programovacím jazyce ''Java'', ''Python'' nebo ''C/C++''. Veřejné testovací soubory - {{:courses:b6b36dsa:ukoly:DSA_HW03.zip?400|DSA_HW03}}. ^ Název úlohy v BRUTE | **HW03** || ^ Odevzdávané soubory | ''hash.py'' – zdrojový soubor v python3 || | ::: | ''Hash.java'' – zdrojový soubor v Java, název třídy Hash || | ::: | ''hash.c'', resp. ''hash.cpp'' – zdrojový soubor v C/Cpp || ^ Argumenty programu | žádné || ^ Kompilace pro jazyk C | clang -Wall -Werror -pedantic -std=c99 clang -Wall -Werror -pedantic -std=c+ +17 || ^ Kompilace a spuštění \\ pro jazyk Java | javac *.java java -classpath Hash || ^ Očekávaná složitost | Změna velikosti tabulky, vkládání, mazání – vše v čase $\mathcal{O}(n)$ || | ::: | Koeficient pro čas výpočtu $1.5$ || ^ Procvičované oblasti | hašování lineární zkoušení (linear probing) otevřené adresování (open addresing) || ^ Bodové hodnocení (celkem 10 bodů) | 2 body | prelude_01 – prelude_08 + 2 skryté testy | | ::: | 2 body | append_01 – append_08 + 6 skrytých testů | | ::: | 3 body | delete_01 – delete_08 + 8 skrytých testů | | ::: | 3 body | timetest_01 – timetest_15 – řešení časově a prostorově stejné nebo lepší \\ než referenční řešení | ^ Maximální počet uploadů | ''20'' Více uploadů je možných s odpovídající bodovou ztrátou ||