\documentclass[]{article}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage{listings}
\usepackage{titling}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{pdfpages}
\usepackage{float}
\usepackage{amssymb}
\usepackage{alltt}
\usepackage{verbatim}
\usepackage{amstext}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{indentfirst}

\usetikzlibrary{arrows}

%opening
\title  {Sortowanie zewnętrzne z wielkimi buforami}
\author {Kacper Donat, \textit{nr indeksu}: 165581}

\begin{document}
	{\huge \noindent \textbf{\thetitle} \vspace{5mm}} \\ 
	{\large \makebox[3cm][l]{\textbf{Temat 21}:} Para liczb rzeczywistych posortowana względem odległości od środka układu współrzędnych.} \\
	{\large \makebox[3cm][l]{\textbf{Autor}:} \theauthor} \\ 
	
	\noindent\hrulefill

    \section{Opis rekordu oraz formatu danych}
    Rekord składa sie z 2 liczb rzeczywistych, przechowywanych jako 2 liczby w formacie \textbf{\tt double}. Rekordy są
    sortowane zgodnie z odległością od środka układu współrzędnych, tj. $r_1 < r_2 \iff |r_1| < |r_2|$. 
    \begin{lstlisting}[language=c]
    typedef struct {
        double x;
        double y;
    } record_t;
    \end{lstlisting}

    Rekordy na taśmie są zapisywane w formacie binarnym jako zrzut pamięci o znaczy, że każdy rekord zajmuje dokładnie 
    16 bajtów pamięci. Rozmiar strony jest ustalony za pomocą stałej \texttt{PAGE\_SIZE}, której domyślna wartość to
    $4096$.

    \begin{alltt}
    0000000 \(\overbrace{\texttt{0000 0000 0000 3ff0}}\sp{x}\) \(\overbrace{\texttt{0000 0000 0000 4000}}\sp{y}\) ; rekord 1
    0000010 0000 0000 0000 0000 0000 0000 0000 3ff0 ; rekord 2
    \end{alltt}

    Na aplikację składają się 4 mniejsze programy służące do wykonywania poszczególnych akcji:
    \begin{itemize}
        \item \texttt{reader}    - odczyt informacji z taśmy w sposób zrozumiały dla człowieka
        \item \texttt{appender}  - zapis informacji na taśmy
        \item \texttt{generator} - generowanie określonej liczby losowych rekordów z podanego zakresu wartości
        \item \texttt{sorter}    - sortowanie taśm
    \end{itemize}

    Instrukcja użycia każdego z programu dostępna po wywołaniu bez żadnych argumentów.

	\section{Zastosowana metoda}
    Do sortowania taśm wykorzystana jest metoda sortowania z wielkimi buforami. Liczbę buforów $n$ można regulować za
    pomocą parametru programu sortującego. Łącznie program wykorzystuje maksymalnie $2n + 2$ buforów o wielkości jednej
    strony. Jest to odpowiednio $n$ taśm tymczasowych służących do zapisu, $n$ taśm przechowujących serie pośrednie oraz
    taśma sortowana i taśma wynikowa.
    
    W trakcie działania programu, maksymalna liczba wykorzystywanych jednocześnie taśm wynosi $n + 1$ - 
    $n$ taśm, z których odczytujemy informacje oraz $1$ wykorzystywana do zapisu informacji.
    
    \section{Przeprowadzone testy}

    W celach testowych wygenerowany pliki o wykładniczo rosnącej wielkości i przetestowano ilość operacji dyskowych
    wykonanych przez program podczas operacji sortowania.

    \begin{table}[H]
        \centering
        \begin{tabular}{r|r|rr|r}
            N      & IO      & Reads   & Writes  & Wartość teoretyczna [IO] \\ \hline
            $0$    & 1       & 1       & 0       & 0                        \\
            $10$   & 6       & 4       & 2       & 0                        \\
            $10^2$ & 6       & 4       & 2       & 0                        \\
            $10^3$ & 18      & 10      & 8       & 8                        \\
            $10^4$ & 162     & 82      & 80      & 79                       \\
            $10^5$ & 1569    & 787     & 782     & 1564                     \\
            $10^6$ & 15668   & 7854    & 7814    & 15626                    \\
            $10^7$ & 234883  & 117694  & 117189  & 234375                   \\
            $10^8$ & 2347790 & 1175915 & 1171875 & 2343750                 
        \end{tabular}
        \caption{Ilości operacji dyskowych dla danych $N$ oraz parametru $b = 256$}
        \label{my-label}
    \end{table}

    \begin{figure}[H]
        \centering

		\begin{tikzpicture}% function
		\begin{loglogaxis}[
            ymin = 0, ymax=3000000,
            axis x line=bottom, axis y line=left,
            xlabel = {$N$}, ylabel = {IO ops},
            width=\linewidth, smooth,
            enlargelimits=false,
            axis line style={-latex},
            anchor=origin,
            mark size=1pt,
            height=12cm,
            clip=false,
            grid=both,
		]
			\addplot[black, thick, mark=*]  table [x=n, y=rw, col sep=comma]{normal.csv};
			\addplot[green, thick, mark=*]  table [x=n, y=r, col sep=comma]{normal.csv};
			\addplot[red, thick, mark=*]    table [x=n, y=w, col sep=comma]{normal.csv};
			\addplot[blue, dashed, mark=*] table [x=n, y=t, col sep=comma]{normal.csv};
		\end{loglogaxis}
		\end{tikzpicture}
		\caption{Ilość operacji dyskowych jako funkcja liczby rekordów $N$}
	\end{figure}

    Jak widać na powyższym wykresie oraz tabeli, operacji jest zawsze więcej niż wskazywałaby na to wartości
    teoretyczne. Wynika to z faktu, że do wyliczenia wartości znamy dokładną wartość $N$ - stąd też nawet jeżeli
    wygenerujemy tylko jedną serię w początkowej fazie, musimy przepisać wyniki na taśmę wynikową. Dodatkowo nie znamy
    granic serii, a w wypadku takiej metody powoduje to dodatkowe odczyty na końcu aby sprawdzić czy nie ma większej
    ilości rekordów w pliku. Stąd z oczekiwanych przez algorytm 8 operacji dla 1000 rekordów (4 odczyty i 4 zapisy)
    dostajemy 8 zapisów (4 na taśmę tymczasową oraz 4 na wynikową) i 10 odczytów (4 z taśmy początkowej, 4 z
    tymczasowej + po 1 wynikającym z sprawdzania końca pliku). Jak jednak można zauważyć dla większych wartości
    odstępstwa te stają się minimalne.
\end{document}