fork(2) download
copy 
  1.  
  2. #include <iostream>
  3. #include <set>
  4. #include <unordered_set>
  5. #include <functional>
  6. #include <chrono>
  7. #include <cmath>
  8. #include <random>
  9. #include <ctime>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. using namespace __gnu_pbds;
  12. using namespace std;
  13.  
  14. typedef gp_hash_table<
  15.     int, null_type, hash<int>, equal_to<int>, direct_mask_range_hashing<int>, linear_probe_fn<>,
  16.     hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>
  17.     gp;
  18.  
  19. typedef cc_hash_table<
  20.     int, null_type, hash<int>, equal_to<int>, direct_mask_range_hashing<int>,
  21.     hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>
  22.     cc;
  23.  
  24. int getTicks() {
  25.     static auto startTime = std::chrono::high_resolution_clock::now();
  26.     auto t = std::chrono::high_resolution_clock::now();
  27.     return std::chrono::duration_cast<std::chrono::milliseconds>(t - startTime).count();
  28. }
  29. template <class T> struct hset {
  30.     size_t sz, (*hfunc)(T);
  31.     static constexpr uint8_t dead = 0, filled = 1, empty = 2;
  32.     uint8_t *state;
  33.     T *x;
  34.     int buffer;
  35.     hset(int s, size_t (*hf)(T) = [](T val) -> size_t {
  36.         hash<T> hfunc;
  37.         return hfunc(val);
  38.     }) {
  39.         hfunc = hf;
  40.         sz = s;
  41.         buffer = 2 * log2(sz) + 5; // a buffer lets us work faster because we don't have to check that pos<sz at the
  42.                                    // cost of a minimal chance of runtime error + a little memory
  43.         state = new uint8_t[sz + buffer];
  44.         x = new T[sz + buffer];
  45.         fill(state, state + sz + buffer, empty);
  46.     }
  47.     ~hset() {
  48.         delete state;
  49.         delete x;
  50.     }
  51.     void clear() { fill(state, state + sz + buffer, empty); }
  52.     bool erase(const T &v) {
  53.         int pos = hfunc(v) % sz;
  54.         while (true) {
  55.             if (state[pos] == empty)
  56.                 return false;
  57.             if (state[pos] == filled && x[pos] == v) {
  58.                 state[pos] = dead;
  59.                 return true;
  60.             }
  61.             pos++;
  62.         }
  63.     }
  64.     void erase_x(const T &v) // UNSAFE! crashes if element is not found
  65.     {
  66.         int pos = hfunc(v) % sz;
  67.         while (true) {
  68.             if (state[pos] == filled && x[pos] == v) {
  69.                 state[pos] = dead;
  70.                 return;
  71.             }
  72.             pos++;
  73.         }
  74.     }
  75.     bool insert(const T &v) {
  76.         int pos = hfunc(v) % sz;
  77.         int first = -1;
  78.         while (true) {
  79.             if (state[pos] != filled) {
  80.                 if (state[pos] == empty) {
  81.                     if (first == -1)
  82.                         first = pos;
  83.                     state[first] = filled;
  84.                     x[first] = v;
  85.                     return true;
  86.                 } else if (first == -1)
  87.                     first = pos;
  88.             } else if (x[pos] == v)
  89.                 return false;
  90.             pos++;
  91.         }
  92.     }
  93.     int count(const T &v) const {
  94.         int pos = hfunc(v) % sz;
  95.         while (true) {
  96.             if (state[pos] == empty)
  97.                 return 0;
  98.             if (state[pos] == filled && x[pos] == v)
  99.                 return 1;
  100.             pos++;
  101.         }
  102.     }
  103.     T *find(const T &v) const {
  104.         int pos = hfunc(v) % sz;
  105.         while (true) {
  106.             if (state[pos] == empty)
  107.                 return NULL;
  108.             else if (state[pos] == filled && x[pos] == v)
  109.                 return &x[pos];
  110.             pos++;
  111.         }
  112.     }
  113.     size_t size() { return sz; }
  114. };
  115. const int n = 2e5;
  116. int a[n], b[n];
  117. void testHSET() {
  118.     hset<int> v(4 * n);
  119.     for (int t = 0; t < 100; t++) {
  120.         for (int i = 0; i < n; i++)
  121.             v.insert(a[i]);
  122.     }
  123.     for (int i = 0; i < n; i++)
  124.         v.erase(b[i]);
  125. }
  126. void testPBuset() {
  127.     gp v;
  128.     v.resize(n);
  129.     v.set_loads({.25, .5});
  130.     for (int t = 0; t < 100; t++) {
  131.         for (int i = 0; i < n; i++)
  132.             v.insert(a[i]);
  133.     }
  134.     for (int i = 0; i < n; i++)
  135.         v.erase(b[i]);
  136. }
  137. void testPBuset2() {
  138.     cc v;
  139.     v.resize(n);
  140.     v.set_loads({.25, .5});
  141.     for (int t = 0; t < 100; t++) {
  142.         for (int i = 0; i < n; i++)
  143.             v.insert(a[i]);
  144.     }
  145.     for (int i = 0; i < n; i++)
  146.         v.erase(b[i]);
  147. }
  148. void teststluset() {
  149.     unordered_set<int> v;
  150.     v.max_load_factor(0.5);
  151.     v.reserve(n);
  152.     for (int t = 0; t < 100; t++) {
  153.         for (int i = 0; i < n; i++)
  154.             v.insert(a[i]);
  155.     }
  156.     for (int i = 0; i < n; i++)
  157.         v.erase(b[i]);
  158. }
  159. #define RANDUZ_MAX 0x0fffffff
  160. int randuz() {
  161.     static std::mt19937 gen(time(NULL));
  162.     static std::uniform_int_distribution<int> d(0, RANDUZ_MAX);
  163.     return d(gen);
  164. }
  165. void testgood() {
  166.     unordered_set<int> s1;
  167.     hset<int> s2(10000, [](int x) -> size_t { return x * x; });
  168.     for (int i = 0; i < 0xfff; i++) {
  169.         s1.insert(i);
  170.         s2.insert(i);
  171.     }
  172.     for (int i = 0; i < 20000; i++) {
  173.         int x = randuz() & 0xfff;
  174.         switch (randuz() % 3) {
  175.         case 0:
  176.             s1.erase(x);
  177.             s2.erase(x);
  178.             break;
  179.         case 1:
  180.             s1.insert(x);
  181.             s2.insert(x);
  182.             break;
  183.         case 2:
  184.             if (s1.count(x) != s2.count(x))
  185.                 cout << "BAD\n";
  186.             break;
  187.         }
  188.     }
  189. }
  190. int main() {
  191.     testgood(); // test to make sure our hash set actually works
  192.     for (int i = 0; i < n; i++)
  193.         a[i] = randuz(), b[i] = randuz();
  194.     ;
  195.     int s = getTicks();
  196.     testHSET();
  197.     int t = getTicks();
  198.     cout << "Custom hash set: " << t - s << "ms\n";
  199.     for (int i = 0; i < n; i++)
  200.         a[i] = randuz(), b[i] = randuz();
  201.     s = getTicks();
  202.     testPBuset();
  203.     t = getTicks();
  204.     cout << "gp_hash_table: " << t - s << "ms\n";
  205.     for (int i = 0; i < n; i++)
  206.         a[i] = randuz(), b[i] = randuz();
  207.     s = getTicks();
  208.     testPBuset2();
  209.     t = getTicks();
  210.     cout << "cc_hash_table: " << t - s << "ms\n";
  211.     for (int i = 0; i < n; i++)
  212.         a[i] = randuz(), b[i] = randuz();
  213.     ;
  214.     s = getTicks();
  215.     teststluset();
  216.     t = getTicks();
  217.     cout << "unordered_set: " << t - s << "ms\n";
  218.     return 0;
  219. }
  220.  
Success #stdin #stdout 1.6s 14700KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Custom hash set: 318ms
gp_hash_table: 168ms
cc_hash_table: 220ms
unordered_set: 846ms
https://ideone.com/N0Wha6
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!