Datové struktury I - NTIN066 - ZS 2015/2016 - 2. úkol

Pravidla

• Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší „inspirace“.
• Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí „inspirací“. Výjimku tvoří odevzdání kódu.
• Úkol a možné postupy řešení můžete probírat s ostatními, avšak respektuje výše uvedené o nesdílení kódu. To znamená: společná diskuse je povolena, ale programujte sami.
• Povolená jsou řešení v jazycích C/C++ (doporučený jazyk), Java a C#.
• Používejte standardní konstrukce svého programovacího jazyka, ale už ne speciální knihovní funkce. Celou datovou strukturu musíte naprogramovat samostatně.
• Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.

Popis problému

Naprogramujte reprezentaci množiny pomocí (2,3)-stromů a (2,4)-stromů. Prvky množiny budou kladná 31-bitová čísla, uložená ve všech vrcholech stromu (nejen v listech).

Prozkoumejte chování obou datových struktur na testovacích datech vygenerovaných níže popsaným programem. Testovací data obsahují množiny různých velikostí se dvěma typy operací:

• rovnoměrný test: posloupnost operací Insert a Delete, která pracuje rovnoměrně se všemi klíči množiny;
• nevyvážený test: nejprve se operacemi Insert od 1 do N vytvoří velká množina, následují operace Insert a Delete na vhodně zvolené malé podmnožině, a nakonec jsou operacemi Delete od 1 do N všechny prvky smazány.

Pro každý test změřte následující veličiny:

• průměrný počet přístupů k vrcholům na jednu operaci (pro každou operaci počítáme, kolika vrcholů se „dotkla“; opakovaný přístup k témuž vrcholu během jedné operace se počítá pouze jednou);
• průměrný počet modifikací vrcholů na jednu operaci (opět pro každou operaci počítáme vrcholy, ale tentokrát jen ty, které byly během operace vytvořeny, smazány nebo změněny).

Pro každý typ testu (rovnoměrný/nevyvážený) nakreslete graf závislosti počtu přístupů a počtu modifikací na velikosti množiny (dvě křivky pro (2,3)-stromy, další dvě pro (2,4)-stromy). Pokuste se zdůvodnit rozdíly mezi chováním obou stromů.

Generování dat

Stáhněte si generátor, případně použijte už zkompilovaný /afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw2/abgen v unixové laboratoři Rotunda. Spusťte ho s následujícími parametry:

• -s XX, kde XX jsou poslední dvě číslice vašeho studentského čísla;
• -b, pokud chcete vygenerovat data pro nerovnoměrný test; jinak se generuje rovnoměrný.

Výstupem generátoru bude textový soubor, každý řádek popisuje jednu operaci na stromu:

• # N: začátek testu pro množinu velikosti N – zrušte starý strom a založte nový (velikost množiny se vám může hodit při kreslení grafů);
• I X: vložení klíče X do stromu (pokud se klíč ve stromu už vyskytuje, operaci ignorujte);
• D X: smazáni klíče X ze stromu (pokud se klíč ve stromu nevyskytuje, operaci ignorujte).

Na jedno spuštění generátor vytvoří sadu testů o velikostech cca 1000 až 1000000 prvků. Pokud chcete při ladění vyrobit jiný test, použijte parametr -n N pro nastavení velikosti množiny.

Příklad vstupu

# 5
I 67
I 45
D 67
I 81

Odevzdáni

Pošlete e-mail s předmětem tvaru 'HW2-55973318' (t.j. HW2-studentské číslo) s těmito přílohami:

• zdrojový text, na kterém jste vše naměřili (pokud je složen z více souborů, zabalte je ZIPem nebo TARem do jednoho),
• PDF s grafy a komentáři.

Tělo e-mailu nechť obsahuje údaje podle tohoto vzoru:

Jmeno: Martin Mareš
Pseudonym pro vysledky na webu: Tomáš Marný
Cviceni: pondeli-12:20-lichy