fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
vector<vector<int>>:
generate: 531.182 ms
walkthrough: 25.8943 ms

vector<pair<int,int>>:
generate: 38.0245 ms
walkthrough: 309.237 ms
https://ideone.com/ogOL7R
language:
C++14 (gcc 8.3)
created:
2 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!