Advertisement
HellFinger

Untitled

Feb 23rd, 2022
27
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void lcg(vector<unsigned int>& r, int seed, int size, unsigned long a, unsigned long c, unsigned long m){
  2. if (size == 1){
  3. r.push_back((a*seed+c)%m);
  4. return;
  5. }
  6. for(int i = 0; i < size; ++i){
  7. r.push_back(0);
  8. }
  9. r[0] = seed;
  10. for(int i = 1; i < size; ++i){
  11. r[i] = uint32_t((a*r[i-1]+c)%m);
  12. }
  13. r.erase(r.begin());
  14. }
  15.  
  16.  
  17.  
  18. void generate(int seed, long size, double a2b, double i2u, vector<unsigned int> & a, vector<unsigned int>& b){
  19. //hardcoded consts for lcg generator
  20. //a = 50001
  21. //c = 49999
  22. //m = 2500000000
  23. int inter = int(size*i2u);
  24. int a_size = int(a2b*size*(1-i2u)/(a2b+1))+inter;
  25. int b_size = int(size*(1-i2u)/(a2b+1))+inter;
  26. lcg(a, seed, a_size, 50001, 49999, 2500000000);
  27. lcg(b, a[a_size - inter],b_size, 50001, 49999, 2500000000);
  28. }
  29.  
  30. void generate_v3_0(int seed, long sizeA, long sizeB, long sizeInter, vector<unsigned int> & a, vector<unsigned int>& b) {
  31. //hardcoded consts for lcg generator
  32. //a = 50001
  33. //c = 49999
  34. //m = 2500000000
  35.  
  36.  
  37. lcg(a, seed, sizeA+1, 50001, 49999, 2500000000);
  38. (sizeA!=sizeInter)?lcg(b, a[sizeA-sizeInter-1], sizeB+1, 50001, 49999, 2500000000):lcg(b, seed, sizeB+1, 50001, 49999, 2500000000);
  39.  
  40. std::shuffle(a.begin(), a.end(), std::default_random_engine(seed+1));
  41. std::shuffle(b.begin(), b.end(), std::default_random_engine(seed+2));
  42. }
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52. //тестер
  53.  
  54. int main(int argc, char* argv[]) {
  55. std::ofstream out;
  56. vector<unsigned int> a;
  57. vector<unsigned int> b;
  58.  
  59.  
  60. /*
  61. 1000
  62. 2000
  63. 5000
  64. 10000
  65. 20000
  66. 50000
  67. 100000
  68. 200000
  69. 500000
  70. 1000000
  71. 2000000
  72. 5000000
  73. 10000000
  74.  
  75. */
  76. int A = 100000;
  77. int B = 100000;
  78. int inter = 10000;
  79. if (argc>1){
  80. A = stoi(argv[1]);
  81. B = stoi(argv[2]);
  82. inter = stoi(argv[3]);
  83.  
  84. }
  85.  
  86. generate_v3_0(14, A, B, inter, a, b);
  87.  
  88.  
  89.  
  90.  
  91. //unordered_set<unsigned int> v_intersection;
  92. /*
  93. sort(a.begin(), a.end());
  94. sort(b.begin(), b.end());
  95.  
  96. BaezaYates_step(&a, &b, a.begin(), a.end(), b.begin(), b.end(), &v_intersection);
  97. */
  98.  
  99. vector<unsigned int> res;
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106. double start_time = getCPUTime();
  107. sort(a.begin(), a.end());
  108. sort(b.begin(), b.end());
  109.  
  110.  
  111. double preprocess_time = getCPUTime();
  112.  
  113.  
  114. GallopingIntersection(a, b, res);
  115.  
  116.  
  117. double end_time = getCPUTime();
  118.  
  119. cout << "Intersection size: " << res.size() << endl; // ' ' << v_intersection.size() << endl;
  120. cout << "Union size: " << A + B - inter << endl;
  121. cout << "A: " << a.size() << " B: " << b.size();
  122. cout << "\nCPU time: " << end_time - start_time;
  123. cout << "\nCPU preprocess time: " << preprocess_time - start_time << endl;
  124.  
  125.  
  126.  
  127. }
  128.  
Advertisement
RAW Paste Data Copied
Advertisement