fork download
  1. #include<bits/stdc++.h>
  2. #include <sys/time.h>
  3.  
  4. using namespace std;
  5. using pi=pair<int,int>;
  6.  
  7. long long get_rand(long long lim,mt19937_64 &eg){
  8. return (long long)(eg()%lim);
  9. }
  10.  
  11. long long start_time;
  12.  
  13. void start_clock(){
  14. struct timeval tv;
  15. gettimeofday(&tv, NULL);
  16. start_time=(tv.tv_sec*1000000+tv.tv_usec);
  17. }
  18.  
  19. long long current_clock(){
  20. struct timeval tv;
  21. gettimeofday(&tv, NULL);
  22. long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  23. long long res=current_time-start_time;
  24.  
  25. // cout << res/1000000 << ".";
  26. // cout << res%1000000 << " sec\n";
  27. return res;
  28. }
  29.  
  30. int main(){
  31. uint_fast64_t seed=1;
  32. mt19937_64 engine(seed);
  33. for(int i=0;i<100000;i++){engine();}
  34.  
  35. int kind=500000;
  36. int elem=5000000;
  37. int exe_time=10;
  38. long long tvv_g=0,tvv_w=0;
  39. long long tpv_g=0,tpv_w=0;
  40.  
  41. for(int exe=0;exe<exe_time;exe++){
  42. vector<int> arr(elem);
  43. for(auto &nx : arr){nx=get_rand(kind,engine);}
  44. vector<int> p(kind);
  45. for(int i=0;i<kind;i++){p[i]=i;}
  46. shuffle(p.begin(),p.end(),engine);
  47.  
  48. // cout << "vector<vector<int>>:\n";
  49. start_clock();
  50. vector<vector<int>> vv(kind+5);
  51. for(int i=0;i<elem;i++){
  52. vv[arr[i]].emplace_back(i);
  53. }
  54. // cout << "generate: ";
  55. tvv_g+=current_clock();
  56.  
  57. start_clock();
  58. int hash1=0;
  59. for(int i=0;i<kind;i++){
  60. int chash=0;
  61. for(auto &nx : vv[i]){
  62. chash+=nx;
  63. chash&=32767;
  64. }
  65. hash1^=(chash<<(i&15));
  66. }
  67. // cout << "walkthrough: ";
  68. tvv_w+=current_clock();
  69.  
  70. // cout << "vector<pair<int,int>>:\n";
  71. start_clock();
  72. int add_point=kind;
  73. vector<pi> pv(kind+elem+5,{-1,-1});
  74. for(int i=0;i<elem;i++){
  75. if(pv[arr[i]].first!=-1){
  76. pv[add_point]=pv[arr[i]];
  77. pv[arr[i]].second=add_point;
  78. add_point++;
  79. }
  80. pv[arr[i]].first=i;
  81. }
  82. // cout << "generate: ";
  83. tpv_g+=current_clock();
  84.  
  85. start_clock();
  86. int hash2=0;
  87. for(int i=0;i<kind;i++){
  88. int chash=0;
  89. int pos=i;
  90. while(pos!=-1 && pv[pos].first!=-1){
  91. chash+=pv[pos].first;
  92. chash&=32767;
  93. pos=pv[pos].second;
  94. }
  95. hash2^=(chash<<(i&15));
  96. }
  97. // cout << "walkthrough: ";
  98. tpv_w+=current_clock();
  99.  
  100. assert(hash1==hash2);
  101. }
  102.  
  103. double output;
  104.  
  105. cout << "vector<vector<int>>:\n";
  106. output=tvv_g;
  107. output/=1000;output/=exe_time;
  108. cout << "generate: " << output << " ms\n";
  109. output=tvv_w;
  110. output/=1000;output/=exe_time;
  111. cout << "walkthrough: " << output << " ms\n";
  112. cout << "\n";
  113.  
  114. cout << "vector<pair<int,int>>:\n";
  115. output=tpv_g;
  116. output/=1000;output/=exe_time;
  117. cout << "generate: " << output << " ms\n";
  118. output=tpv_w;
  119. output/=1000;output/=exe_time;
  120. cout << "walkthrough: " << output << " ms\n";
  121. return 0;
  122. }
  123.  
Success #stdin #stdout 11.24s 119120KB
stdin
Standard input is empty
stdout
vector<vector<int>>:
generate: 531.182 ms
walkthrough: 25.8943 ms

vector<pair<int,int>>:
generate: 38.0245 ms
walkthrough: 309.237 ms