127 lines
5.8 KiB
TeX
127 lines
5.8 KiB
TeX
\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}
|