Advertisement
HellFinger

Untitled

May 22nd, 2022
989
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include "cpu_bench.hpp"
  3. #include "stdc++.h"
  4. #include "set_generator.hpp"
  5.  
  6.  
  7. using namespace std;
  8. void split(vector<unsigned int>& s, vector<vector<unsigned int>>& sub, int n){
  9.   vector<unsigned int>::iterator splitter = s.begin();
  10.   while(s.end() >= splitter + n){
  11.       sub.push_back(vector<unsigned int>(splitter ,splitter + n));
  12.       splitter += n;
  13.   }
  14.   if(s.end() - splitter > 0){
  15.     sub.push_back(vector<unsigned int>(splitter, s.end()));
  16.   }
  17.  
  18. }
  19.  
  20.  
  21. void preprocessHash64(vector<unsigned int>::iterator s, vector<unsigned int>::iterator e, vector<vector<unsigned int>>& h_m, bitset<64>& bit){
  22.  
  23.  
  24.   unordered_map<unsigned int, unsigned int> h;
  25.   vector<unsigned int>::const_iterator i = s;
  26.   int buf_h;
  27.  
  28.  
  29.   while(i < e){
  30.     buf_h = *i%64;
  31.     bit[buf_h] = true;
  32.     h[*i] = buf_h;
  33.     h_m[buf_h].push_back(*i);
  34.     ++i;
  35.   }
  36.  
  37.  
  38. }
  39.  
  40. void preprocessor64(vector<unsigned int>& s){
  41.   sort(s.begin(), s.end());
  42.  
  43.  
  44. }
  45.  
  46. void IntersectSmall64(bitset<64>& bA, vector<vector<unsigned int>>&v_mA, bitset<64>& bB, vector<vector<unsigned int>>&v_mB, vector<unsigned int>& res){
  47.   bitset<64> bAnd = bA&bB;
  48.  
  49. for(int i = bAnd._Find_first(); i < bAnd.size(); i = bAnd._Find_next(i)){
  50.     set_intersection(v_mA[i].begin(), v_mA[i].end(), v_mB[i].begin(), v_mB[i].end(), back_inserter(res));
  51. }
  52.  
  53.  
  54. }
  55.  
  56. void dk_intersection64(vector<unsigned int>& sA, vector<unsigned int>& sB,  vector<unsigned int>& result){
  57.   int p,q;
  58.   p = 0;
  59.   q = 0;
  60.   vector<vector<unsigned int>> h_rA;
  61.   vector<vector<unsigned int>> h_rB;
  62.   for (int i = 0; i < 64; ++i){
  63.     h_rA.push_back(vector<unsigned int>());
  64.     h_rB.push_back(vector<unsigned int>());
  65.   }
  66.   int leftoutA;
  67.   int leftoutB;
  68.  
  69.  
  70.   bitset<64> bit_A;
  71.   bitset<64> bit_B;
  72.  
  73.   while(p < sA.size() && q < sB.size()){
  74.       leftoutA = std::min(8, int(sA.size()-p));
  75.       leftoutB = std::min(8, int(sB.size()-q));
  76.       if (sA[p] > sB[q+leftoutB-1]){
  77.  
  78.         q += leftoutB;
  79.  
  80.  
  81.       }
  82.       else if(sA[p+leftoutA-1] < sB[q]){
  83.         p += leftoutA;
  84.  
  85.       }
  86.       else{
  87.  
  88.         preprocessHash64(sA.begin() + p, sA.begin()+p+leftoutA, h_rA, bit_A);
  89.         preprocessHash64(sB.begin() + q, sB.begin()+q+leftoutB, h_rB, bit_B);
  90.         IntersectSmall64(bit_A, h_rA, bit_B, h_rB, result);
  91.  
  92.         for(int i = 0; i <h_rA.size(); ++i){
  93.           vector<unsigned int>().swap(h_rA[i]);
  94.           vector<unsigned int>().swap(h_rB[i]);
  95.         }
  96.         bit_A.reset();
  97.         bit_B.reset();
  98.  
  99.  
  100.         if (sA[p+leftoutA-1] < sB[q+leftoutB-1]){
  101.           p += leftoutA;
  102.  
  103.         }
  104.         else{
  105.           q += leftoutB;
  106.         }
  107.       }
  108.   }
  109.  
  110.  
  111. }
  112.  
  113.  
  114. int main(int argc, char* argv[]){
  115.   int A = 100000;
  116.   int B = 100000;
  117.   int inter = 10000;
  118.  
  119.   if (argc>1){
  120.     A = stoi(argv[1]);
  121.     B = stoi(argv[2]);
  122.     inter = stoi(argv[3]);
  123.   }
  124.  
  125.   vector<uint32_t> a;
  126.   vector<uint32_t> b;
  127.   vector<uint32_t> res;
  128.  
  129.  
  130.   generate_v3_0(14, A, B, inter, a, b);
  131.   cout << "generated\n";
  132.  
  133.   vector<vector<unsigned int>> subsetsA;
  134.   vector<vector<unsigned int>> subsetsB;
  135.  
  136.   vector<bitset<64>> bitmasksA;
  137.   vector<bitset<64>> bitmasksB;
  138.  
  139.  
  140.   vector<vector<vector<unsigned int>>> h_rA;
  141.   vector<vector<vector<unsigned int>>> h_rB;
  142.  
  143.  
  144.  
  145.   auto start_time = getCPUTime();
  146.  
  147.   preprocessor64(a);
  148.   preprocessor64(b);
  149.  
  150.   dk_intersection64(a, b, res);
  151.  
  152.  
  153.   auto end_time = getCPUTime();
  154.  
  155.   cout << "Intersection size: " << res.size() << endl; // ' ' << v_intersection.size() << endl;
  156.   cout << "Union size: " << A + B - inter << endl;
  157.   cout << "A: " << a.size() << " B: " << b.size() << endl;
  158.  
  159.   std::cout << std::fixed << std::showpoint;
  160.   cout << "\nCPU time: " << setprecision(15) << end_time - start_time;
  161.  
  162.   fprintf( stderr, "\nCPU time:%lf\n", (end_time - start_time) );
  163.   fprintf( stderr, "%lf ", (end_time - start_time) )
  164. }
  165.  
Advertisement
RAW Paste Data Copied
Advertisement