A4: WIP

6 files changed, 512 insertions, 0 deletions

diff --git a/a4/Makefile b/a4/Makefile
new file mode 100644
index 0000000..dc61cde
--- /dev/null
+++ b/a4/Makefile
@@ -0,0 +1,4 @@
+all: list_vs_vector
+
+list_vs_vector: list_vs_vector.cc Makefile octave.cc
+	g++ -fcoroutines -O2 -Wall -Werror -Wextra -Wconversion -std=c++20 octave.cc $< -o $@
diff --git a/a4/exercise.tex b/a4/exercise.tex
new file mode 100644
index 0000000..11def5d
--- /dev/null
+++ b/a4/exercise.tex
@@ -0,0 +1,25 @@
+\title{A4: List vs Vector}
+\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.
+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.
+
+\bigskip
+
+\begin{figure}
+  \includegraphics[scale=0.95]{a4/insert.pdf}
+\end{figure}
+
+\begin{figure}
+  \includegraphics[scale=.95]{a4/remove.pdf}
+\end{figure}
+
+\end{document}
diff --git a/a4/generator.h b/a4/generator.h
new file mode 100644
index 0000000..c857a40
--- /dev/null
+++ b/a4/generator.h
@@ -0,0 +1,86 @@
+// -*- c++ -*-
+#pragma once
+
+// The code in this file has been taken directly from:
+// https://en.cppreference.com/w/cpp/language/coroutines
+
+#include <coroutine>
+#include <cstdint>
+#include <exception>
+#include <iostream>
+
+template <typename T>
+struct Generator
+{
+	// The class name 'Generator' is our choice and it is not required for coroutine
+	// magic. Compiler recognizes coroutine by the presence of 'co_yield' keyword.
+	// You can use name 'MyGenerator' (or any other name) instead as long as you include
+	// nested struct promise_type with 'MyGenerator get_return_object()' method.
+
+	struct promise_type;
+	using handle_type = std::coroutine_handle<promise_type>;
+
+	struct promise_type // required
+	{
+		T value_;
+		std::exception_ptr exception_;
+
+		Generator get_return_object()
+		{
+			return Generator(handle_type::from_promise(*this));
+		}
+		std::suspend_always initial_suspend() { return {}; }
+		std::suspend_always final_suspend() noexcept { return {}; }
+		void unhandled_exception() { exception_ = std::current_exception(); } // saving
+		// exception
+
+		template <std::convertible_to<T> From> // C++20 concept
+		std::suspend_always yield_value(From&& from)
+		{
+			value_ = std::forward<From>(from); // caching the result in promise
+			return {};
+		}
+		void return_void() { }
+	};
+
+	handle_type h_;
+
+	Generator(handle_type h)
+		: h_(h)
+	{
+	}
+	~Generator() { h_.destroy(); }
+	explicit operator bool()
+	{
+		fill(); // The only way to reliably find out whether or not we finished coroutine,
+		        // whether or not there is going to be a next value generated (co_yield)
+		        // in coroutine via C++ getter (operator () below) is to execute/resume
+		        // coroutine until the next co_yield point (or let it fall off end).
+		        // Then we store/cache result in promise to allow getter (operator() below
+		        // to grab it without executing coroutine).
+		return !h_.done();
+	}
+	T operator()()
+	{
+		fill();
+		full_ = false; // we are going to move out previously cached
+		// result to make promise empty again
+		return std::move(h_.promise().value_);
+	}
+
+private:
+	bool full_ = false;
+
+	void fill()
+	{
+		if (!full_)
+		{
+			h_();
+			if (h_.promise().exception_)
+				std::rethrow_exception(h_.promise().exception_);
+			// propagate coroutine exception in called context
+
+			full_ = true;
+		}
+	}
+};
diff --git a/a4/list_vs_vector.cc b/a4/list_vs_vector.cc
new file mode 100644
index 0000000..1665e3e
--- /dev/null
+++ b/a4/list_vs_vector.cc
@@ -0,0 +1,262 @@
+#include <limits>
+#include <random>
+#include <iostream>
+#include <vector>
+#include <list>
+#include <set>
+#include <chrono>
+#include <type_traits>
+
+#include "generator.h"
+#include "octave.h"
+
+template<typename T>
+Generator<T> get_random(int seed,
+                        T min = std::numeric_limits<T>::min(),
+                        T max = std::numeric_limits<T>::max())
+{
+	std::default_random_engine generator(seed);
+	// Randomly generate T-values from the range [min; max]
+	std::uniform_int_distribution<T> distrib(min, max);
+
+	while(true)
+	{
+		co_yield distrib(generator);
+	}
+}
+
+class Timer
+{
+public:
+	void start()
+	{
+		_start = std::chrono::high_resolution_clock::now();
+	}
+
+	void stop()
+	{
+		_elapsed = std::chrono::high_resolution_clock::now() - _start;
+		std::cout << " took " << _elapsed.count() * 1000 << "ms\n";
+	}
+
+	double elapsed() const
+	{
+		return _elapsed.count() * 1000; // return number of milliseconds passed
+	}
+
+private:
+	std::chrono::time_point<std::chrono::high_resolution_clock> _start{};
+	std::chrono::duration<double> _elapsed{};
+};
+
+class Measure
+{
+public:
+	Measure(Timer& timer)
+		: timer(timer)
+	{
+		timer.start();
+	}
+
+	~Measure()
+	{
+		timer.stop();
+	}
+
+private:
+	Timer& timer;
+};
+
+template<typename C, typename T>
+void sorted_insert(C& container, T element)
+{
+	auto it = std::begin(container);
+	while(it != std::end(container) && *it < element)
+	{
+		++it;
+	}
+
+	container.insert(it, element);
+}
+
+template<typename C>
+void remove_index(C& container, int index)
+{
+	auto it = std::begin(container);
+	for(int i = 0; i < index; ++i)
+	{
+		++it;
+	}
+
+	container.erase(it);
+}
+
+int main()
+{
+	Timer timer;
+	Octave ins_oct("insert");
+	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");
+	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};
+
+	for(auto N : Ns)
+	{
+		ins_plot_v.setX(double(N));
+		ins_plot_l.setX(double(N));
+		ins_plot_s.setX(double(N));
+
+		rem_plot_v.setX(double(N));
+		rem_plot_l.setX(double(N));
+		rem_plot_s.setX(double(N));
+
+		for(int i = 0; i < 3; ++i)
+		{
+			// Create N unique values in rnd vector:
+			std::vector<int> rnd;
+			auto gen = get_random<int>(i, 0, int(N) * 10);
+			while(rnd.size() < N)
+			{
+				auto r = gen();
+				if(std::find(rnd.begin(), rnd.end(), r) == std::end(rnd))
+				{
+					rnd.push_back(r);
+				}
+			}
+
+			// Create vector of removal indices
+			std::vector<int> rem;
+			{
+				std::default_random_engine generator(i);
+				for(int end = int(N) - 1; end >= 0; --end)
+				{
+					// Gradually decrease the range of valid removal indices
+					std::uniform_int_distribution<int> distrib(0, end);
+					rem.push_back(distrib(generator));
+				}
+
+				if(N < 64)
+				{
+					std::cout << "rem:";
+					for(auto i : rem)
+					{
+						std::cout << " " << i;
+					}
+					std::cout << '\n';
+				}
+			}
+
+			// std::vector experiment
+			{
+				std::vector<int> vec;
+				std::cout << "std::vector insert (N=" + std::to_string(N) + "):\n";
+				{
+					Measure _(timer);
+					for(auto r : rnd)
+					{
+						sorted_insert(vec, r);
+					}
+				}
+				ins_plot_v.add(timer.elapsed());
+
+				if(N < 64)
+				{
+					std::cout << "vec:";
+					for(auto i : vec)
+					{
+						std::cout << " " << i;
+					}
+					std::cout << '\n';
+				}
+
+				std::cout << "std::vector remove (N=" + std::to_string(N) + "):\n";
+				{
+					Measure _(timer);
+					for(auto r : rem)
+					{
+						remove_index(vec, r);
+					}
+				}
+				rem_plot_v.add(timer.elapsed());
+			}
+
+			// std::list experiment
+			{
+				std::list<int> lst;
+				std::cout << "std::list insert (N=" + std::to_string(N) + "):\n";
+				{
+					Measure _(timer);
+					for(auto r : rnd)
+					{
+						sorted_insert(lst, r);
+					}
+				}
+				ins_plot_l.add(timer.elapsed());
+
+				if(N < 64)
+				{
+					std::cout << "lst:";
+					for(auto i : lst)
+					{
+						std::cout << " " << i;
+					}
+					std::cout << '\n';
+				}
+
+				std::cout << "std::list remove (N=" + std::to_string(N) + "):\n";
+				{
+					Measure _(timer);
+					for(auto r : rem)
+					{
+						remove_index(lst, r);
+					}
+				}
+				rem_plot_l.add(timer.elapsed());
+			}
+
+			// std::set experiment
+			{
+				std::set<int> set;
+				std::cout << "std::set insert (N=" + std::to_string(N) + "):\n";
+				{
+					Measure _(timer);
+					for(auto r : rnd)
+					{
+						set.insert(r);
+					}
+				}
+				ins_plot_s.add(timer.elapsed());
+
+				if(N < 64)
+				{
+					std::cout << "set:";
+					for(auto i : set)
+					{
+						std::cout << " " << i;
+					}
+					std::cout << '\n';
+				}
+
+				std::cout << "std::set remove (N=" + std::to_string(N) + "):\n";
+				{
+					Measure _(timer);
+					for(auto r : rem)
+					{
+						remove_index(set, r);
+					}
+				}
+				rem_plot_s.add(timer.elapsed());
+			}
+		}
+	}
+}
diff --git a/a4/octave.cc b/a4/octave.cc
new file mode 100644
index 0000000..e48fe6c
--- /dev/null
+++ b/a4/octave.cc
@@ -0,0 +1,90 @@
+#include "octave.h"
+
+const Plot& operator<<(std::ostream& out, const Plot& plot)
+{
+	out << "x = [ ";
+	for(const auto& [x,y] : plot.data)
+	{
+		out << x << " ";
+	}
+	out << "]\n";
+
+	out << "y = [ ";
+	for(const auto& [x,y] : plot.data)
+	{
+		out << y << " ";
+	}
+	out << "]\n";
+	out << "scatter(x, y)\n";
+	return plot;
+}
+
+const std::string& Plot::getTitle() const
+{
+	return title;
+}
+
+void Plot::add(const std::pair<double, double>& point)
+{
+	data.push_back(point);
+}
+
+void Plot::add(double y)
+{
+	if(y < 1000.0)
+	{
+		add({x, y});
+	}
+}
+
+void Plot::setX(double x)
+{
+	this->x = x;
+}
+
+Octave::Octave(const std::string& file)
+	: out(file + ".m")
+	, file(file)
+{
+}
+
+Octave::~Octave()
+{
+	if(!out.good())
+	{
+		return;
+	}
+
+	out << "fig = figure()\n";
+	out << "hold on;\n";
+
+	for(const auto& plot : plots)
+	{
+		out << plot;
+	}
+
+	out << "legend ({";
+	for(const auto& plot : plots)
+	{
+		out << "'" << plot.getTitle() << "' " ;
+	}
+	out << "}, 'location', 'east');\n";
+	out << "xlabel ('" << x_axis << "');\n";
+	out << "ylabel ('" << y_axis << "');\n";
+//	out << "set(gca, 'yscale', 'log')\n";
+	out << "set(gcf, 'PaperPosition', [0 0 5 5])\n";
+	out << "set(gcf, 'PaperSize', [5 5])\n";
+	out << "print(fig, '" << file << ".pdf');\n";
+}
+
+Plot& Octave::add(const std::string& title)
+{
+	plots.push_back(title);
+	return plots.back();
+}
+
+void Octave::setAxis(const std::string& x_axis, const std::string& y_axis)
+{
+	this->x_axis = x_axis;
+	this->y_axis = y_axis;
+}
diff --git a/a4/octave.h b/a4/octave.h
new file mode 100644
index 0000000..3c814c5
--- /dev/null
+++ b/a4/octave.h
@@ -0,0 +1,45 @@
+// -*- c++ -*-
+#pragma once
+
+#include <string>
+#include <utility>
+#include <fstream>
+#include <vector>
+#include <deque>
+
+class Plot
+{
+public:
+	Plot(const std::string& title) : title(title) {}
+
+	const std::string& getTitle() const;
+	void add(const std::pair<double, double>& point);
+	void add(double y);
+	void setX(double x);
+
+	friend const Plot& operator<<(std::ostream& out, const Plot& plot);
+
+private:
+	std::vector<std::pair<double, double>> data;
+	std::string title;
+	double x{};
+};
+
+class Octave
+{
+public:
+	Octave(const std::string& file);
+	~Octave();
+
+	Plot& add(const std::string& title);
+	void setAxis(const std::string& x_axis, const std::string& y_axis);
+
+private:
+	std::deque<Plot> plots;
+	std::ofstream out;
+
+	std::string x_axis;
+	std::string y_axis;
+
+	std::string file;
+};