fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6.  
  7. using namespace __gnu_pbds;
  8. typedef pair<int, int> pii;
  9. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
  10. typedef cc_hash_table<int, int, hash<int>> ht;
  11. // typedef cc_hash_table<
  12. //     int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>,
  13. //     hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>
  14. //     ht;
  15.  
  16. bool eraseVals = false;
  17. void benchmarkPolicy(string msg, vector<pii> &vals, int NUM_ITERS) {
  18.     clock_t begin = clock();
  19.     ht test;
  20.     for (int t = 0; t < NUM_ITERS; t++) {
  21.         for (auto i : vals) {
  22.             test[i.first] = test[i.first] + i.second * t;
  23.         }
  24.     }
  25.     cout << msg << ": " << string(60 - msg.size(), ' ') << "\t" << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  26. }
  27.  
  28. void benchmarkStl(string msg, vector<pii> &vals, int NUM_ITERS) {
  29.     clock_t begin = clock();
  30.     unordered_map<int, int> test;
  31.     for (int t = 0; t < NUM_ITERS; t++) {
  32.         for (auto i : vals) {
  33.             test[i.first] = test[i.first] + i.second * t;
  34.         }
  35.     }
  36.     cout << msg << ": " << string(60 - msg.size(), ' ') << "\t" << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  37. }
  38.  
  39. void benchmark(string msg, vector<pii> vals, int NUM_ITERS) {
  40.     benchmarkStl("unordered map " + msg, vals, NUM_ITERS);
  41.     benchmarkPolicy("policy hash table " + msg, vals, NUM_ITERS);
  42.     cout << endl;
  43. }
  44.  
  45. vector<pii> generateVec(int max_val, bool shuffled) {
  46.     vector<int> k(max_val), v(max_val);
  47.     vector<pii> vals;
  48.     iota(k.begin(), k.end(), 0);
  49.     iota(v.begin(), v.end(), 0);
  50.     if (shuffled) {
  51.         random_shuffle(k.begin(), k.end());
  52.         random_shuffle(v.begin(), v.end());
  53.     }
  54.     for (int i = 0; i < max_val; i++) {
  55.         vals.push_back({k[i], v[i]});
  56.     }
  57.     return vals;
  58. }
  59. int main() {
  60.     ios::sync_with_stdio(0);
  61.     cin.tie(0);
  62.     benchmark("linear insertion", generateVec(1e7, false), 1);
  63.     benchmark("linear read/write", generateVec(1e5, false), 1000);
  64.     benchmark("random insertion", generateVec(1e7, true), 1);
  65.     benchmark("random read/write", generateVec(1e5, true), 1000);
  66. }
Time limit exceeded #stdin #stdout 5s 750812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
unordered map linear insertion:                               	0.765515
policy hash table linear insertion:                           	0.466836

unordered map linear read/write:                              	1.80801
policy hash table linear read/write:                          	0.227539
https://ideone.com/ZkNMbH
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!