fork(2) download
  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
stdin
Standard input is empty
stdout
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