\documentclass[a4paper,10pt]{article}

\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[czech]{babel}
\usepackage{fontenc}
\usepackage{bbm}
%\usepackage[dvips,pdftex,draft]{graphicx}
\usepackage{fancyhdr} %zahlavi a zapati
\usepackage{a4wide} % širší stránka
\usepackage{todonotes}
\presetkeys{todonotes}{inline}{}
\usepackage{graphicx}
\usepackage{float}
\usepackage{hyperref}

%\usepackage[dvips,pdftex]{hyperref}

\author{Studentus Maximus}

\begin{document}

% záhlaví vlevo
  \lhead{0. DÚ -- Nafukovací pole}
% záhlaví uprostřed
  \chead{Datové Struktury I}
% záhlaví vpravo -- jméno
  \rhead{Studentus Maximus}
% nastavíme použití toho stylu
  \pagestyle{fancy}

	\todo{
		Takto jsou zobrazeny poznámky cvičících k~tomu, co a jak je tu napsáno, skutečný text je mimo oranžové rámečky.
	}

	Počítač, na kterém byly provedeny testy: Procesor Intel(R) Core(TM) i7-5557U CPU @ 3.10GHz, RAM 16GB.
	
	Operační systém: Debian 8
	
	Překlad: clang++ verze 3.8, optimalizace -O2.
\todo{Konfigurace počítače je důležitá zejména pro měření času.
	Důležitými parametry jsou: verze procesoru a velikost RAM.
	Model procesoru můžete na linuxu zjistit příkazem {\tt{cat /proc/cpuinfo}}.
	Tyto parametry uvádíme proto, aby všechny testy byly opakovatelné.
}

	\section{Test 1 -- naivní vs standardní}

	\subsection{Standardní implementace}

  \todo{Je povoleno kouknout se do zdrojového kódu nebo výstupu generátoru a zjistit, co měříme.}
	První graf (Obrázek~\ref{fig:1_standard}) zobrazuje průměrný počet kroků na jednu operaci pro různé typy testů a standardní implementaci vektoru.
	V~sekvenčním testu jsme postupně vložili $n$ prvků a následně jsme je zase všechny odebrali.
	Ve zbývajících dvou testech jsme nejprve vložili $n$ (respektive nejbližší nižší mocninu dvojky) prvků a poté jsme udělali $10n$ náhodných operací v~případě náhodného testu nebo jsme $10n$-krát provedli posloupnost dvou vložení a dvou odebrání prvků v~případě extrémního testu.
	Z~přednášky víme, že amortizovaná cena jedné operace push nebo pop je konstantní.
	\todo{Odhadneme asymptotickou složitost operace.}
	Z~grafu naměřených hodnot můžeme vidět, že u~všech typů a všech provedených měření lze průměrný počet kroků na jednu operaci shora odhadnout konstantou, což souhlasí s~tvrzením z~přednášky.
	\todo{
		Pozor, že děláme odhady toho, co jsme naměřili.
    V~žádném případě z~naměřených dat nedostáváme důkaz, že se datová struktura bude chovat dle našich představ i pro vyšší, než námi naměřené hodnoty.
		Dokonce ani pro měřené velikosti nedostáváme horní odhad chovaní datové struktury (mohou existovat horší posloupnosti operací).
		Takové tvrzení by bylo třeba zdůvodnit (důkazem z~přednášky, intuicí\dots).
	}

	\todo{Odhadneme multiplikativní konstantu.}
	Z~grafu pro sekvenční test můžeme shora odhadnout multiplikativní konstantu okolo 2.2 kroku na operaci.
	Povšimněme si, že vektor dosahoval mnohem lepších výsledků pro náhodný a extrémní test, kde bylo průměrně na operaci potřeba udělat 1.1 kroku.
	\todo{
		Kdybychom do kroků nezapočítávali vložení prvků, ale pouze každé překopírování prvku, při změně velikosti vektoru, pak by nám konstanta vyšla zhruba 0.2, což je menší než 1.
		V~některých domácích úkolech se tohle může stát.
	}

	\todo{Všimneme si, co je v~grafech za zvláštnosti a pokusíme se je zdůvodnit.}
	U~všech tří křivek si můžeme všimnout, že přibližně na mocninách dvojky dojde k~prudkému nárůstu počtu kroků, který se potom postupně snižuje k~další mocnině dvojky.
	Nejvíce se toto chování projevuje u~sekvenčního testu.
	Domnívám se, že je to způsobeno tím, že pro tuto velikost dojde k~alokaci většího pole a překopírování prvků mezi novým a starým polem.
	Při vkládání více prvků do již alokované volné paměti není potřeba alokovat více místa a proto se průměrný počet kroků na operaci snižuje.
	U~náhodného a extrémního testu nepozoruji v grafech tak výrazné skoky.
	Myslím si, že jsou způsobeny úvodní inicializační fází.
	Poté se udělá spousta operací, které nevyvolají realokaci, a tudíž dojde k zjemnění skoků z inicializační fáze.
	
	Dále si můžeme všimnout, že pro velmi malé velikosti množiny standardní implementace v~sekvenčním i extrémním testu o~trošku roste, ale na druhou stranu v~náhodném testu trošku klesá.
	Myslím, že je to dané jednak tím, že jsme úvodní velikost vektoru zvolili osm, to se projeví zejména v~testech, při kterých se velikost vektoru jen zvětšuje a pak jen zmenšuje.
	Dalším vlivem může být to, že pro malé vektory je větší pravděpodobnost několika operací push a několika operací pop tak, že se velikost vektoru změní (pokud stojíme v~nule a podle hodu mincí jdeme o~krok vpravo nebo vlevo, pak v~100 krocích častěji dojdeme do 10 než do 80).
	\todo{
		V~tomto případě je zdůvodnění nad rámec znalostí z~přednášky a základní pochopení chování datové struktury, proto jej není nutné uvádět.
	}


	\subsection{Naivní implementace}
	
	\todo{Přidáváme i graf s~logaritmickou škálou, protože nárůst počtu kroků v~extrémním případě způsobí, že ostatní křivky jsou příliš blízko nule a nejsou vidět.}
	Na dalších třech grafech (Obrázek~\ref{fig:1_naive},~\ref{fig:1_naive_log} a~\ref{fig:1_naive_log_extreme}) můžeme pozorovat chování naivní implementace.
	V~grafu naivní implementace (Obrázek~\ref{fig:1_naive}) můžeme vidět, že na rozdíl od správné implementace průměrný počet kroků na jednu operaci v~našem měření roste v~extrémním testu lineárně s~velikostí držené množiny.
	Multiplikativní konstanta se pohybuje mezi jednou polovinou a jednou čtvrtinou (viz Obrázek~\ref{fig:1_naive_log_extreme}).

	Myslím si, že k~lineárnímu nárůstu dochází díky tomu, že struktura je nucena často přealokovávat celé pole.
  Domnívám se, že k~tomu dochází díky vhodně zvolené velikosti držené množiny (vždy držíme množinu velikosti nejbližší menší mocniny dvojky) a posloupnosti příkazů (střídání operace push a pop).

	Rozdílné je také chování u~náhodného testu, ve kterém se v~případě naivní implementace objevují mnohem větší peaky, pokud velikost držené množiny je přibližně mocnina dvojky.
	Výšku peaků bychom z~grafu mohli odhadnout pomocí odmocniny z~$n$ s~multiplikativní konstantou $\frac{3}{10}$.
	Tato funkce je znázorněna v~grafu (Obrázek~\ref{fig:1_naive_log_extreme}) šedou křivkou.
	Toto celkem sedí s~teorií náhodných procházek na celých číslech.\todo{
		Všimnout si jevu je třeba a je třeba to napsat!
		Zdůvodnění mimo selského rozumu, znalostí z Bc. studia a z~přednášek třeba není, proto zmínka o~náhodných procházkách není nutná.
		V~tomto konkrétním případě není nutný ani odhad rychlosti růstu jako odmocnina.
		Za chybné zdůvodnění nebo odhad asymptotiky nejspíš nestrhneme víc bodů než za chybějící zdůvodnění.
	}
	Ideální by nejspíš bylo změřit tyto hodnoty i okolo větších mocnin dvojky, ale bylo by velmi časově náročné to udělat pro více než dvě další.
	\todo{
		Návrh dalších experimentů testujících naše hypotézy také není špatný.
	}

	Také si můžeme všimnout drobného nárůstu naivní implementace viditelného na Obrázku~\ref{fig:1_naive}.
	Nevím, čím je toto způsobené.
	\todo{Není třeba zdůvodnit naprosto všechno, jen to, co se přímo týká teorie nebo je jednoduše vymyslitelné.}
	
	\subsection{Shrnutí}

	V~sekvečních testech vykazovaly obě struktury podobné vlastnosti, ale v~ostatních testech se chovala standardní struktura lépe.
	Nejvýraznější byl rozdíl v~extrémním testu, ve kterém standardní implementace dosahovala konstantní složitosti okolo 1.06, zatímco naivní implementace roste lineárně v~závislosti na velikosti držené množiny.
	V~náhodném testu dosahovaly obě struktury shodných výsledků, vyjma případů, kdy velikost držené mocniny byla okolo mocniny 2.
	V~těchto případech si v naměřených výsledcích správná struktura udržovala konstantní průměr počtu kroků na jednu operaci, zatímco v~případě naivní struktury průměr rostl s~odmocninou velikosti množiny.

	
	\section{Test 2 -- push s~různými $c$}

	Z grafů znovu pozorujeme kolísání na mocninách nafukovacího parametru $c$ (předtím bylo pozorováno na mocninách $c = 2$) a pak pozvolné klesání.
	Vysvětlení je obdobné, na mocnině $c$ znovu alokujeme a pak přidáváme další prvky do prázdného místa, ale nic za ně nealokujeme, pouze jejich počtem dělíme.

	Všechny křivky bych odhadl zdola zhruba jako $1 + \frac{1}{c-1}$ a shora přibližně $2 + \frac{1}{c-1}$, což odpovídá právě alokaci na mocninách $c$ a větě z přednášky, pro několik hodnot vyobrazeno na Obrázku~\ref{fig:2_codhady}.

	Jak jsme si řekli na přednášce, i pro malá $c > 1$ dynamické pole může fungovat, ale se zmenšujícím odstupem $c$ od jedničky rychle ztrácíme efektivitu.
	Dle naměřených výsledků datovou strukturu výrazně nezrychlíme, pokud přenastavíme hodnotu $c$ ze dvou na vyšší, avšak v takovém případě alokujeme velké množství paměti.

	Pozorování byla provedena na základě Obrázku~\ref{fig:2}.
	\todo{
		Logaritmické měřítko uvádíme jen pro ukázku.
	}

  \section{Měření času}

    Pro obě měření bereme stejnou sekvenci a pětkrát měříme průměrnou dobu jedné operace.

    V grafu měření času standardní implementace (Obrázek~\ref{fig:3stand}) vidíme, že se hodnoty pohybují více méně v malém konstantním rozmezí. 
		Průměrný čas na operaci se pohybuje mezi $2 \cdot 10^{-9}$ a $3 \cdot 10^{-9}$, což odpovídá teorii dokázané na přednášce, že cena jedné operace je amortizovaně konstantní.
    Díky opakování měření vidíme, že jednotlivé měření není přesné a projevuje se náhodnost (daná měřením na reálném počítači).
    
    V grafu měření naivní implementace (Obrázek~\ref{fig:3naive}) jsou náhodné odchylky zanedbatelné vzhledem k průměrné délce trvání jedné operace.
    Největší naměřená hodnota je zhruba 10000-krát větší než hodnota pro stejně velké pole u standardní implementace.
    Celkově tento graf tvarem odpovídá grafu na Obrázku~\ref{fig:1_both}, odůvodnění je stejné jako pro simulaci.

  \section{Grafy}

  \subsection{Grafy Test 1}

	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph1_standard.pdf}
	 \caption{Správná implementace.}
		\label{fig:1_standard}
	\end{figure}

	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph1_naive.pdf}
	 \caption{Naivní implementace.}
		\label{fig:1_naive}
	\end{figure}
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph1_naive_log.pdf}
	 \caption{Naivní implementace v~logaritmické škále.}
		\label{fig:1_naive_log}
	\end{figure}
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph1_naive_extreme.pdf}
	 \caption{Naivní implementace spolu s křivkami odhadů v logaritmické škále.}
		\label{fig:1_naive_log_extreme}
	\end{figure}

	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph1_both.pdf}
	 \caption{Naivní vs správná implementace.}
		\label{fig:1_both}
	\end{figure}
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph1_both_log.pdf}
	 \caption{Naivní vs správná implementace v logaritmické škále.}
		\label{fig:1_both_logscale}
	\end{figure}

  \subsection{Grafy 2}

	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph2.pdf}
		\caption{Různé zvětšování alokovaného prostoru, standardní implementace.}
		\label{fig:2}
	\end{figure}

	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph2_codhady.pdf}
		\caption{Různé zvětšování alokovaného prostoru, standardní implementace, spolu s odhady konstant.}
		\label{fig:2_codhady}
	\end{figure}
	
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph2_logscale_y.pdf}
		\caption{Různé zvětšování alokovaného prostoru, standardní implementace a logaritmická škála na ose $y$.}
		\label{fig:2logscaley}
	\end{figure}
	
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph2_logscale_x.pdf}
	 \caption{Různé zvětšování alokovaného prostoru.}
		\label{fig:2logscalex}
	\end{figure}
	
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.8]{figs/graph2_logscale_both.pdf}
	 \caption{Různé zvětšování alokovaného prostoru.}
		\label{fig:2logscale_both}
	\end{figure}

  \subsection{Grafy čas}
	
	\begin{figure}[H]
		\centering
    \includegraphics[scale=0.8]{figs/standartd.pdf}
	 \caption{Standardní implementace.}
		\label{fig:3stand}
	\end{figure}
	
	\begin{figure}[H]
		\centering
    \includegraphics[scale=0.8]{figs/naive.pdf}
	 \caption{Naivní implementace.}
		\label{fig:3naive}
	\end{figure}

\end{document}
