Datové struktury 1 - NTIN066 - ZS 2014/2015
2. úkol
Termín odevzdání: 13. listopadu 2014.
Způsob odevzdání: odesláním do CodExu a odesláním v příloze emailem na ds1@kam.mff.cuni.cz.
CodEx pro odevzdání této úlohy je již k dispozici.
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.
- Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.
Popis problému
Naimplementujte Splay stromy. Napište program, který přečte ze vstupu testovací data a vypíše počet vložených prvků a průměrnou délku cesty prošlé při operacích Find, pro každý běh dat.
Pro poslední běh též vypíše, kolikrát jednotlivé operace Find prošly cestu dané délky.
Vstupní data jsou rozdělená na běhy, každý běh začíná sérií operací Insert, po které následuje série operací Find. Řádky Insert začínají písmenem I, řádky Find
začínají písmenem F, poslední řádek běhu obsahuje písmeno R. Za posledním během je řádek s písmenem X. Vkládané prvky tvoří interval [0,n-1]. Po každém běhu
se strom vyprázdní.
Pomocí unixového programu /afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl2-gen-data dostupného v laboratoři Rotunda vygenerujte zkušební data, spusťte na nich
své programy a výslednou statistiku zašlete jako součást řešení uloženou v běžném formátu. Dále též sebraná data zpracujte do grafu, například pomocí programu Excel nebo gnuplot.
Každý graf by měl obsahovat pět křivek, první graf má osu x indexovanou počtem vložených prvků a na ose y je průměrná doba Find, druhý graf má na ose x délku cesty
a na ose y počet, kolikrát se daná délka vyskytla u operace Find.
Příklad vstupu
I 1
I 2
I 0
F 1
F 0
F 2
R
I 2
I 3
I 0
I 1
F 2
F 0
F 1
F 3
R
X
Možný smyšlený výstup
3 1
4 1.75
1 1
2 3
Náčrt možných grafů
Generování zkušebních dat
$/afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl2-gen-data XX N
vygeneruje data pro měření, kde XX jsou poslední
dvě číslice z vašeho studentského čísla a N je jedno z {0,10,100,1000,10000}.
Když N=0, data provádí Find na všechna vložená čísla v náhodném pořadí, když N>0,
data opakovaně vyhledávají náhodnou podmnožinu zvolených čísel velikosti N, každé z nich cca 100-krát.
Velikost běhu začíná na 1 000 prvcích a roste až do 1 000 000 prvků. Je cca 300 běhů. Příklad spuštění:
pbl2-gen-data 72 0 | muj-splay > data-0.out
pbl2-gen-data 72 10 | muj-splay > data-10.out
pbl2-gen-data 72 100 | muj-splay > data-100.out
pbl2-gen-data 72 1000 | muj-splay > data-1000.out
pbl2-gen-data 72 10000 | muj-splay > data-10000.out
Výsledky
Výsledky jednotlivých lidí jsou zaznamenány u výsledků úlohy 1.
Příklady odevzdaných grafů:
Jiří Dutkevič
Petr Fejfar
Ukázkový graf druhého přednášejícího V. Čunáta.