Datové struktury I – 0. úkol

Termín odevzdání: kdykoliv
Způsob odevzdání: pomocí webového rozhraní na https://kam.mff.cuni.cz/~ds1/
Obecná pravidla: Prečtěte si je důkladně

Popis problému

Naprogramujte dvě varianty nafukovacího pole, standardní variantu z přednášky, kde při plném zaplnění pole dochází k zvýšení jeho velikosti na dvojnásobek, a naopak při nejvýše čtvrtinovém zaplnění se pole zmenší na polovinu. Implementujte také druhé, naivní nafukovací pole, které se zvětšuje 2-krát, ale zmenšuje se už při uvolnění poloviny velikosti pole.

V druhé části změřte, jaký vliv na počet kroků operace push má konstanta, kterou násobíme velikost při zvětšování. Vytvořte tedy pole, která se budou zvětšovat c-krát pro c = 1.1 1.2 1.4 1.7 2 2.5 3 4

Prozkoumejte chování obou datových struktur na testovacích datech vygenerovaných níže popsaným programem. Testy se skládají z operací push a pop definovaných na přednášce (obdoba push_back a pop_back).

Pro každý test změřte počet operací (push a pop) a počet kroků, kde krok je změna jedné buňky (přidání čísla do pole, každé překopírování prvku při nafukování nebo snižování velikosti pole).

Generování dat

Pro vygenerování testovacích dat si stáhněte generátor. Spusťte ho s následujícími parametry:

• -s XX, kde XX jsou poslední dvě číslice vašeho studentského čísla;
• -n N, kde se provede N operací push a pak N operací pop;
• -r N, kde se provede N operací push a N operací pop v náhodném pořadí;
• -e N, kde se provede N operací push a N operací pop v zákeřném pořadí;
• -i N, kde se provede pouze N operací push;

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

• N: začátek testu pro parametr N (parametr použijte při kreslení grafů);
• I X: vložení klíče X na konec nafukovacího pole, operace push(X);
• P: smazání posledního prvku pole, operace pop() (generátor může vytvářet vstupy volající pop na prázdné pole, pak pop nic neprovede).

Výstupní grafy

Volte vhodná měřítka, naměřené hodnoty a pozorované jevy komentujte. Pokuste se odhadnout nejen asymptotické chování počtu kroků, ale i multiplikativní konstanty u nejvyšších členů složitosti (to, co schovává O).

Test 1 -- naivní vs standardní:

Změřte počet kroků a potřebný čas standardního a naivního nafukovacího pole na generátoru s příslušnými parametry. Zavolejte tedy:

• ./generator -s 42 -n N
• ./generator -s 42 -r N
• ./generator -s 42 -e N

Test 2 -- push s různými c:

Změřte počet kroků a potřebný čas nafukovacího pole, které se nafukuje c-krát pro všechna c z {1.1 1.2 1.4 1.7 2 2.5 3 4}. Zavolejte tedy:

• ./generator -s 42 -i N

Pro každý typ testu nakreslete graf závislosti počtu kroků na parametru N.

Pro test s parametrem e nakreslete graf závislosti průměrné doby trvání jedné operace na parametru N (pro několik vhodných voleb parametru N).

Pro první test:

• Nakreslete do jednoho grafu počty kroků pro standardní nafukovací pole.
• Do druhého grafu nakreslete počty kroků pro naivní nafukovací pole.
• Spojený graf 1. a 2.

To samé pro naměřené časy.

Druhý test:

• Nakreslete do grafu křivky, pro každé c z {1.1 1.2 1.4 1.7 2 2.5 3 4}.
• Do druhého grafu nakreslete potřebné časy zase pro každé c z {1.1 1.2 1.4 1.7 2 2.5 3 4}.

Vysvětlete tvary křivek v obou testech a zdůvodněte rozdíly mezi chováním obou implementací polí.

Příklad vstupu

5
P
P
I 4
P
P
I 3
I 2
P
I 1
I 1

Poznámky

Na našem počítači běží každý test méně než 20 minut. Pokud Vám některý z testů běží více než stokrát déle, tak zkuste vymyslet efektivnější postup.