HellFinger

Untitled

May 22nd, 2022 (edited)
901
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <chrono>
  3. #include <unordered_set>
  4. #include <random>
  5. #include <vector>
  6. #include <iomanip>
  7. #include "hash_wrappers.h"
  8. #include "cpu_and_wall_time.h"
  9. #include "cpu_bench.hpp"
  10. #include <thread>
  11.  
  12. using namespace std;
  13.  
  14.  
  15.  
  16. mutex mtx;
  17.  
  18. //--------------Генерация множеств-------------------//
  19.  
  20. void lcg(vector<unsigned int>& r, int seed, int size, unsigned long a, unsigned long c, unsigned long m){
  21.   if (size == 1){
  22.     r.push_back((a*seed+c)%m);
  23.     return;
  24.   }
  25.   for(int i = 0; i < size; ++i){
  26.     r.push_back(0);
  27.   }
  28.   r[0] = seed;
  29.   for(int i = 1; i < size; ++i){
  30.     r[i] = uint32_t((a*r[i-1]+c)%m);
  31.   }
  32.   r.erase(r.begin());
  33. }
  34.  
  35.  
  36.  
  37. void generate_v3_0(int seed, long sizeA, long sizeB, long sizeInter, vector<unsigned int> & a, vector<unsigned int>& b) {
  38. //hardcoded consts for lcg generator
  39. //a = 50001
  40. //c = 49999
  41. //m = 2500000000
  42.  
  43.  
  44. lcg(a, seed, sizeA+1, 50001, 49999, 2500000000);
  45. (sizeA!=sizeInter)?lcg(b, a[sizeA-sizeInter-1], sizeB+1, 50001, 49999, 2500000000):lcg(b, seed, sizeB+1, 50001, 49999, 2500000000);
  46.  
  47. std::shuffle(a.begin(), a.end(), std::default_random_engine(seed+1));
  48. std::shuffle(b.begin(), b.end(), std::default_random_engine(seed+2));
  49. }
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65. //------------ Хешевое пересечение--------------//
  66. class Hasher
  67. {
  68. public:
  69.   uint32_t operator() (uint32_t const& key) const
  70.   {
  71.       hfl::FarmHash64Wrapper wrap;
  72.       uint32_t hash = wrap(key);
  73.       return hash;
  74.   }
  75. };
  76.  
  77. class HasherMUR
  78. {
  79. public:
  80.   uint32_t operator() (uint32_t const& key) const
  81.   {
  82.       hfl::MurmurHash64AWrapper wrap;
  83.       uint32_t hash = wrap(key);
  84.       return hash;
  85.   }
  86. };
  87.  
  88. class HasherCITY
  89. {
  90. public:
  91.   uint32_t operator() (uint32_t const& key) const
  92.   {
  93.       hfl::CityHash64Wrapper wrap;
  94.       uint32_t hash = wrap(key);
  95.       return hash;
  96.   }
  97. };
  98.  
  99. void unordered_intersectionSONS(unordered_set<uint32_t, Hasher> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C, vector<uint32_t>::iterator b_begin, vector<uint32_t>::iterator b_end){
  100.  
  101.     vector<uint32_t>::iterator bIt = b_begin;
  102.  
  103.   while(bIt != b_end){
  104.     if(A_hashed.count(*bIt) >0){
  105.       mtx.lock();
  106.       C.push_back(*bIt);
  107.       mtx.unlock();
  108.     }
  109.     ++bIt;
  110.   }
  111. }
  112.  
  113.  
  114. void unordered_intersectionFATHER(unordered_set<uint32_t, Hasher> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C){
  115.   vector<uint32_t>::iterator b_mid = B.begin() + B.size()/2;
  116.  
  117.   std::thread threadStart(unordered_intersectionSONS, ref(A_hashed), ref(B), ref(C), B.begin(), b_mid);
  118.   std::thread threadEnd(unordered_intersectionSONS, ref(A_hashed), ref(B), ref(C), b_mid, B.end());
  119.   threadStart.join();
  120.   threadEnd.join();
  121.  
  122. }
  123.  
  124. void unordered_intersection(unordered_set<uint32_t, HasherCITY> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C){
  125.  
  126.  
  127.   vector<uint32_t>::iterator bIt = B.begin();
  128.  
  129.   while(bIt != B.end()){
  130.  
  131.     //(A_hashed.find(*bIt) != A_hashed.end())?C.push_back(*bIt):void();
  132.  
  133.    
  134.     if(A_hashed.count(*bIt) >0){
  135.       C.push_back(*bIt);
  136.     }
  137.    
  138.     ++bIt;
  139.   }
  140.  
  141. }
  142.  
  143. void unordered_intersection(unordered_set<uint32_t, HasherMUR> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C){
  144.  
  145.  
  146.   vector<uint32_t>::iterator bIt = B.begin();
  147.  
  148.   while(bIt != B.end()){
  149.  
  150.     //(A_hashed.find(*bIt) != A_hashed.end())?C.push_back(*bIt):void();
  151.  
  152.    
  153.     if(A_hashed.count(*bIt) >0){
  154.       C.push_back(*bIt);
  155.     }
  156.    
  157.     ++bIt;
  158.   }
  159.  
  160. }
  161.  
  162.  
  163. int main(int argc, char* argv[]) {
  164.  
  165.  
  166.   int A = 100000;
  167.   int B = 100000;
  168.   int inter = 10000;
  169.  
  170.   if (argc>1){
  171.     A = stoi(argv[1]);
  172.     B = stoi(argv[2]);
  173.     inter = stoi(argv[3]);
  174.   }
  175.  
  176.   vector<uint32_t> a;
  177.   vector<uint32_t> b;
  178.   vector<uint32_t> res;
  179.  
  180.  
  181.   generate_v3_0(14, A, B, inter, a, b);
  182.   cout << "generated\n";
  183.  
  184.  
  185.   //cpu_times times_preprocess;
  186.   //cpu_times times_done;
  187.  
  188.   //cpu_timer timer;
  189.   auto start_wall = std::chrono::steady_clock::now();
  190.   auto start_time = getCPUTime();
  191.  
  192.   unordered_set<uint32_t, HasherMUR> A_hashed(a.begin(), a.end());
  193.  
  194.   //times_preprocess = timer.elapsed();
  195.  
  196.   auto preprocess_time = getCPUTime();
  197.   auto preprocess_wall = std::chrono::steady_clock::now();
  198.  
  199.   unordered_intersection(A_hashed, b, res);
  200.  
  201.   //times_done = timer.elapsed();
  202.  
  203.  
  204.  
  205.   auto end_time = getCPUTime();
  206.   auto end_wall = std::chrono::steady_clock::now();
  207.  
  208.   auto elapsedTime = std::chrono::duration_cast<std::chrono::microseconds>(end_wall - start_wall);
  209.   auto elapsedPreproc = std::chrono::duration_cast<std::chrono::microseconds>(preprocess_wall - start_wall);
  210.   cout << "Intersection size: " << res.size() << endl; // ' ' << v_intersection.size() << endl;
  211.   cout << "Union size: " << A + B - inter << endl;
  212.   cout << "A: " << a.size() << " B: " << b.size() << endl;
  213.  
  214.   //std::cout << std::fixed << std::showpoint;
  215.   //cout << "\nCPU time: " << setprecision(15) << end_time - start_time;
  216.   //cout << "\nCPU preprocess time: " << setprecision(15) << preprocess_time - start_time<< endl;
  217.  
  218.   //cout << setprecision(15) << end_time << endl;
  219.   //cout << setprecision(15) << start_time << endl;
  220.   fprintf( stderr, "\nCPU time:%lf\n", (end_time - start_time) );
  221.   fprintf( stderr, "CPU preprocess time:%lf\n", (preprocess_time - start_time) );
  222.   fprintf( stderr, "\nWall time:%lf\n", elapsedTime.count()/1000000.0);
  223.   fprintf( stderr, "Wall preprocess time:%lf\n", elapsedPreproc.count()/1000000.0);
  224.  
  225.  
  226.  
  227.  
  228.   //cout << "\nWALL time: " << setprecision(15) << elapsedTime.count()/1000000 << endl;
  229.   //cout << "\nWALL preprocess time: " << setprecision(15) << elapsedPreproc.count()/100000 << endl;
  230.  
  231.  fprintf( stderr, "%lf ", (end_time - start_time) );
  232.  fprintf( stderr, "%lf ",  (preprocess_time - start_time));
  233.  fprintf( stderr, "%lf ", elapsedTime.count()/1000000.0);
  234.  fprintf( stderr, "%lf ",  elapsedPreproc.count()/1000000.0);
  235.  
  236. }
RAW Paste Data Copied