diff options
Diffstat (limited to 'report')
| -rw-r--r-- | report/report.tex | 53 |
1 files changed, 26 insertions, 27 deletions
diff --git a/report/report.tex b/report/report.tex index 977914c..bf9eefe 100644 --- a/report/report.tex +++ b/report/report.tex @@ -84,11 +84,11 @@ theoretical runtimes and evaluate each implementation. \section{Design} \subsection{Program Flow} -The program is structured into four main phases: +The program is structured into four main \textit{phases}: \noindent \textbf{selecting} an algorithm, \textbf{converting} the inputfile to the array -format, \textbf{sorting} that array, and \textbf{printing} the array to +format, \textbf{sorting} that array, and \textbf{writing} the array to \textit{stdout}. \smallskip @@ -97,11 +97,8 @@ Each \textit{phase} is designed to handle a specific task, which creates modularity and clarity. Within each \textit{phase} a set of functions manage the corresponding operations, allowing the programmer to focus on one task at a time. This design also greatly supports \textit{debugging} by simplifying -tracking and solving errors. -\smallskip - -\noindent -The flowchart below visualize each step. +tracking and solving errors. The flowchart at \autoref{fig:flowchart}, +visualizes this process. \begin{figure}[H] \centering @@ -114,7 +111,7 @@ The flowchart below visualize each step. \textbf{Parsing the data:} After reading the input, the received file is to be \textit{parsed}, meaning that only useful data will be extracted. This will in turn significantly simplify \textit{iteration} through the data, by ensuring -that only meaningful are left. +that only meaningful data is left. \smallskip \noindent @@ -136,10 +133,10 @@ program to be extended with new algorithms if needed. \noindent \textbf{Generating output:} The last step of the program is converting the -parsed data back into a format that can be printed. +parsed data back into a format that can be written to \textit{stdout}. \subsection{Input and Output format} -Each line contains one and only one coordinate consisting of two values +Each line contains one pair of coordinates consisting of two coordinate values formatted as \texttt{$\langle$x$\rangle$\textbackslash t$\langle$y$\rangle$\textbackslash n}, where \texttt{x} and \texttt{y} are non-negative integers in the range 0 to 32767. @@ -243,7 +240,7 @@ modules, where each module is a collection of closely related functions. \noindent For example \texttt{array\_maker.s} contains functions meant to parse data and convert it to the array format. All functions in this program follow the -\textit{x86 calling conventions}, which adding more features a lot easier. +\textit{x86 calling conventions}, which makes adding more features a lot easier. \smallskip \noindent @@ -326,7 +323,7 @@ into two segments. \noindent In order to compare two values in the array. The algorithm \textit{dereferences} -the sub-array, and access the element at the given \textit{index}. +the sub-array, and accesses the element at the given \textit{index}. \smallskip \noindent @@ -367,13 +364,14 @@ To convert the binary digit to its \textit{ASCII} character, we simply add the \smallskip \noindent -The algorithm downside is getting each digit in \textit{reverse} order, which +The algorithms downside is getting each digit in \textit{reverse} order, which means we need to start right side of the \textit{buffer} when adding new digits, as to not \textit{overwrite} previous digits. \smallskip \noindent -So each digit needs to be shifted down to \textit{leftmost} position in memory. +So each digit needs to be shifted down to the \textit{leftmost} position in +memory. \bigskip \noindent @@ -420,27 +418,28 @@ as copying strings, as it encodes a potentially lengthy loop into a \section{Evaluation} To evaluate whether our program works, we created three \textit{shell scripts}, one for generating test data (\textit{generate\_test\_data.sh}), one for testing -the validity of the output of the program (\textit{test.sh}) and one for testing -the execution time of the program (\textit{benchmark.sh}). +the validity of the output from the program (\textit{test.sh}) and one for +testing the execution time of the program (\textit{benchmark.sh}). \smallskip \noindent -The script that generates test files, generates files of with the sizes +The script that generates test files, generates files with the sizes $\{1000n\mid 0\leq n\leq 100\}$. The size is equivalent to the number of coordinates. For each $n$ we also create three different kinds of test files. One where all of the data is random, one where the data is already sorted, and one where it is reversely sorted.\footnote{We also did run it for $n=$ 1 million with random, but to get a pretty plot we decided to omit these values, so it was -not too sparse. Quicksort ran for 0.159s and Insertionsort ran for 386.935s. -This makes Quicksort roughly 2400 times faster than Insertionsort.} +not too sparse. Quicksort ran for 0.159s and insertionsort ran for 386.935s. +This makes quicksort roughly 2400 times faster than insertionsort.} \smallskip \noindent This way we can see both the average case, and worst case of any algorithm we decide to use. Now we can use our \textit{test.sh} script, which runs the program with each of the generated test files for all sorting algorithms of the -program, and compares the output with the output from the \textit{GNU Core -Utilities} program \textit{sort}. +program, and outputs the result to a temporary file. It can then use the python +script \textit{check.py}, which checks if the second argument is a valid sorting +of the first argument given. \subsection{Benchmarking} Given all of the tests pass, we can then run \textit{benchmark.sh}, which times @@ -454,7 +453,7 @@ n)$ and $\mathcal O(n^2)$, is shown on \autoref{fig:benchmarktime}. \begin{tikzpicture} \begin{axis}[ xlabel={size({$n$})}, - ylabel={seconds}, + ylabel={time($s$)}, ymode=log, % xmode=log, width=\textwidth, @@ -502,10 +501,10 @@ n)$ and $\mathcal O(n^2)$, is shown on \autoref{fig:benchmarktime}. \smallskip \noindent -From \autoref{fig:benchmarktime} we see that Insertionsort behaves as expected +From \autoref{fig:benchmarktime} we see that insertionsort behaves as expected with a best-case runtime of $\mathcal O(n)$ when the input is sorted, and a worst-case runtime of $\mathcal O(n^2)$, when the input reversely sorted or -random. We also see that Quicksort behaves as expected with a best-case runtime +random. We also see that quicksort behaves as expected with a best-case runtime of $\mathcal O(n\log n)$ when the input is random, and a worst-case runtime of $\mathcal O(n^2)$ when the input is either sorted or reversely sorted. \smallskip @@ -513,8 +512,8 @@ $\mathcal O(n^2)$ when the input is either sorted or reversely sorted. \noindent It is however also possible to count the number of comparisons for each algorithm. This plot can be seen on \autoref{fig:benchmarkcomp}. Here we clearly -see that, for example, Insertionsort has exactly $n$ comparisons, when sorting -and already sorted array of $n$ elements. We also see that Quicksort with random +see that, for example, insertionsort has exactly $n$ comparisons, when sorting +an already sorted array of $n$ elements. We also see that quicksort with random elements, matches - within a scalar - with $n\log n$. \begin{figure}[H] @@ -522,7 +521,7 @@ elements, matches - within a scalar - with $n\log n$. \begin{tikzpicture} \begin{axis}[ xlabel={size({$n$})}, - ylabel={seconds}, + ylabel={time($s$)}, ymode=log, % xmode=log, width=\textwidth, |