diff options
Diffstat (limited to 'a4/list_vs_vector.cc')
| -rw-r--r-- | a4/list_vs_vector.cc | 262 |
1 files changed, 262 insertions, 0 deletions
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()); + } + } + } +} |