From 6a8ae2de4261fecd0281685b9eea66bbd82bd7fb Mon Sep 17 00:00:00 2001
From: Bent Bisballe Nyeng <deva@aasimon.org>
Date: Tue, 1 Aug 2023 08:27:01 +0200
Subject: A4: WIP

---
 a4/list_vs_vector.cc | 262 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 262 insertions(+)
 create mode 100644 a4/list_vs_vector.cc

(limited to 'a4/list_vs_vector.cc')

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());
+			}
+		}
+	}
+}
-- 
cgit v1.2.3