bogolyubskiyalexey

hse seminar: hash vs tree

Sep 15th, 2020
712
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <set>
  5. #include <unordered_set>
  6. #include <deque>
  7.  
  8. #include <chrono>
  9. #include <random>
  10. using namespace std::chrono;
  11.  
  12. template <typename T, class Z = typename T::value_type>
  13. T create_set(Z upTo) {
  14.     T t;
  15.     std::mt19937 gen;
  16.     gen.seed(12345);
  17.     for (Z i = 1; i <= upTo; i++) {
  18.         t.insert(gen());
  19.     }
  20.     return t;
  21. }
  22.  
  23.  
  24.  
  25. template<typename T>
  26. void timedFunc(typename T::value_type count) {
  27.     auto startTime = steady_clock::now();
  28.     create_set<T>(count);
  29.     auto endTime = steady_clock::now();
  30.     auto elapsed_ms = duration_cast<milliseconds>(endTime - startTime);
  31.     std::cout << "size=" << count << "\telapsed: " << elapsed_ms.count() << " ms\n";
  32. }
  33.  
  34. struct MyHash {
  35.     std::size_t operator()(int value) const noexcept {
  36.         return value;
  37.     }
  38. };
  39.  
  40. int main() {
  41.     std::vector<int> sizes = { 1, 2, 4, 5, 10 };
  42.     std::cout << "set" << std::endl;
  43.     for (int size : sizes) {
  44.         timedFunc<std::set<int>>(size * 1000'000);
  45.    }
  46.  
  47.    std::cout << "unordered_set" << std::endl;
  48.    for (int size : sizes) {
  49.        timedFunc<std::unordered_set<int, MyHash>>(size * 1000'000);
  50.     }
  51.  
  52. }
RAW Paste Data