diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | a4/exercise.tex | 52 | ||||
| -rw-r--r-- | a4/list_vs_vector.cc | 94 | ||||
| -rw-r--r-- | a4/octave.cc | 2 |
4 files changed, 115 insertions, 37 deletions
@@ -26,7 +26,9 @@ A4: zip ${PRE}$@.zip a4/Makefile zip ${PRE}$@.zip a4/*.cc zip ${PRE}$@.zip a4/*.h -# zip ${PRE}$@.zip a4/console.log + zip ${PRE}$@.zip a4/*.log + zip ${PRE}$@.zip a4/*.m + (cd a4; for m in *.m; do octave $${m}; done) xelatex -halt-on-error -jobname=${PRE}$@ a4/exercise.tex xelatex -halt-on-error -jobname=${PRE}$@ a4/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log diff --git a/a4/exercise.tex b/a4/exercise.tex index 11def5d..af53ea5 100644 --- a/a4/exercise.tex +++ b/a4/exercise.tex @@ -2,24 +2,66 @@ \input{preamble.tex} I wanted to experiment with co-routine generator for the random -numbers but discovered the \texttt{std::generator} is not supported -for my compiler. +numbers but discovered the \texttt{std::generator} is not supplied +with my compiler. Instead I found what seemed like a similar implementation here: \texttt{https://en.cppreference.com/w/cpp/language/coroutines}, which I have copied to the \texttt{generator.h} file for use in my program. -I am aware that the random number generator already kind-of works like -a co-routine generator seen from the outside, so the whole experiment -is a bit pointless from a software design perspective. +I am aware that the random number generator already kind-of works +similarly to a co-routine generator seen from the outside, so the +whole experiment is a bit pointless from a software design perspective. + +For this exercise I also re-designed my measurement tool from the +previous assignments to better support re-use of data across +measurements. + +And, finally, I made a class for storing and outputting measurement +points as octave/matlab programs for easier inclusion into the report. +This I put in its own file \texttt{octave.cc} with corresponding +header \texttt{octave.h}. It is by no means very clever, but made to +suit my needs for this assignment. \bigskip +The random number generation for use in insertion I used the +co-routine as described above, inserting, while checking if the number +already exists. +For the ditto for removal indices, I used +a \texttt{uniform\_distribution} thereby being able to gradually +reduce the span as the container would be expected to shrink 1 in size +for each iteration. +Both random number generators were seeded with the iterator number +(each size is being tested three times) to make sure the three +iterations use unique sets of numbers. + +For the smaller sizes of \texttt{N} (the number of items to be +inserted/removed) i print out the numbers to verify their correctness. + + + \begin{figure} \includegraphics[scale=0.95]{a4/insert.pdf} + \caption{Insert of int} + \label{insert} \end{figure} \begin{figure} \includegraphics[scale=.95]{a4/remove.pdf} + \caption{Removal of int} + \label{remove} +\end{figure} + +\begin{figure} + \includegraphics[scale=0.95]{a4/insert-padded.pdf} + \caption{Insert of padded-int (1024 bytes pr. value)} + \label{insert-padded} +\end{figure} + +\begin{figure} + \includegraphics[scale=.95]{a4/remove-padded.pdf} + \caption{Removal of padded-int (1024 bytes pr. value)} + \label{remove-padded} \end{figure} \end{document} diff --git a/a4/list_vs_vector.cc b/a4/list_vs_vector.cc index 1665e3e..22e40b7 100644 --- a/a4/list_vs_vector.cc +++ b/a4/list_vs_vector.cc @@ -91,24 +91,72 @@ void remove_index(C& container, int index) container.erase(it); } +struct PaddedInt +{ + PaddedInt(int i) : i(i) {} + int operator=(int other) + { + i = other; + return i; + } + + bool operator<(int other) const + { + return i < other; + } + + bool operator<(const PaddedInt& other) const + { + return i < other.i; + } + + int i; + char padding[1024 - sizeof(int)]{}; // pad up to 1k +}; + +std::ostream& operator<<(std::ostream& s, const PaddedInt& i) +{ + s << i.i; + return s; +} + +template<typename C> + requires std::is_same<C, std::vector<PaddedInt>>::value || + std::is_same<C, std::list<PaddedInt>>::value || + std::is_same<C, std::set<PaddedInt>>::value || + std::is_same<C, std::vector<int>>::value || + std::is_same<C, std::list<int>>::value || + std::is_same<C, std::set<int>>::value +std::ostream& operator<<(std::ostream& s, const C& container) +{ + for(const auto& item : container) + { + s << item << " "; + } + return s; +} + int main() { + //using experiment_type_t = int; + using experiment_type_t = PaddedInt; + Timer timer; - Octave ins_oct("insert"); + Octave ins_oct("insert-padded"); ins_oct.setAxis("N", "time (ms)"); auto& ins_plot_v = ins_oct.add("std::vector"); auto& ins_plot_l = ins_oct.add("std::list"); auto& ins_plot_s = ins_oct.add("std::set"); - Octave rem_oct("remove"); + Octave rem_oct("remove-padded"); rem_oct.setAxis("N", "time (ms)"); auto& rem_plot_v = rem_oct.add("std::vector"); auto& rem_plot_l = rem_oct.add("std::list"); auto& rem_plot_s = rem_oct.add("std::set"); - constexpr std::size_t Ns[]{10, 50, 100, 200, 500, 1000, 5000, 10'000, 15'000, 20'000, 25'000}; + constexpr std::size_t Ns[]{10, 50, 100, 200, 500, 1000, 2000, 3000, 4000, 5000, 8000, 10'000, 12'000, 14'000, 16'000, 18'000, 20'000}; for(auto N : Ns) { @@ -122,6 +170,7 @@ int main() for(int i = 0; i < 3; ++i) { + std::cout << "--- Iteration " << i << " of 3\n"; // Create N unique values in rnd vector: std::vector<int> rnd; auto gen = get_random<int>(i, 0, int(N) * 10); @@ -134,6 +183,11 @@ int main() } } + if(N < 64) + { + std::cout << "rnd: " << rnd << '\n'; + } + // Create vector of removal indices std::vector<int> rem; { @@ -147,18 +201,13 @@ int main() if(N < 64) { - std::cout << "rem:"; - for(auto i : rem) - { - std::cout << " " << i; - } - std::cout << '\n'; + std::cout << "rem: " << rem << '\n'; } } // std::vector experiment { - std::vector<int> vec; + std::vector<experiment_type_t> vec; std::cout << "std::vector insert (N=" + std::to_string(N) + "):\n"; { Measure _(timer); @@ -171,12 +220,7 @@ int main() if(N < 64) { - std::cout << "vec:"; - for(auto i : vec) - { - std::cout << " " << i; - } - std::cout << '\n'; + std::cout << "vec: " << vec << '\n'; } std::cout << "std::vector remove (N=" + std::to_string(N) + "):\n"; @@ -192,7 +236,7 @@ int main() // std::list experiment { - std::list<int> lst; + std::list<experiment_type_t> lst; std::cout << "std::list insert (N=" + std::to_string(N) + "):\n"; { Measure _(timer); @@ -205,12 +249,7 @@ int main() if(N < 64) { - std::cout << "lst:"; - for(auto i : lst) - { - std::cout << " " << i; - } - std::cout << '\n'; + std::cout << "lst: " << lst << '\n'; } std::cout << "std::list remove (N=" + std::to_string(N) + "):\n"; @@ -226,7 +265,7 @@ int main() // std::set experiment { - std::set<int> set; + std::set<experiment_type_t> set; std::cout << "std::set insert (N=" + std::to_string(N) + "):\n"; { Measure _(timer); @@ -239,12 +278,7 @@ int main() if(N < 64) { - std::cout << "set:"; - for(auto i : set) - { - std::cout << " " << i; - } - std::cout << '\n'; + std::cout << "set: " << set << '\n'; } std::cout << "std::set remove (N=" + std::to_string(N) + "):\n"; diff --git a/a4/octave.cc b/a4/octave.cc index e48fe6c..2d9a239 100644 --- a/a4/octave.cc +++ b/a4/octave.cc @@ -31,7 +31,7 @@ void Plot::add(const std::pair<double, double>& point) void Plot::add(double y) { - if(y < 1000.0) + //if(y < 1000.0) { add({x, y}); } |