Advertisement
HellFinger

Untitled

Dec 17th, 2021
31
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <bitset>
  3. #include <vector>
  4. #include <set>
  5. #include <unordered_set>
  6. #include <unordered_map>
  7. #include <algorithm>
  8. #include "cpu_bench.hpp"
  9. #include <string>
  10. #include <iomanip>
  11.  
  12. //Алгосы
  13. using namespace std;
  14.  
  15.  
  16. void haSetIntersectionhInter(vector<int>& A,vector<int>& B, vector<int>& result)
  17. {
  18. set<int> hs;
  19.  
  20. // Insert the elements of arr1[] to set S
  21. for (int i = 0; i < A.size(); ++i){
  22. hs.insert(A[i]);
  23. }
  24. for (int i = 0; i < B.size(); ++i){
  25.  
  26. // If element is present in set then
  27. // push it to vector V
  28. if (hs.find(B[i]) != hs.end()){
  29. result.push_back(B[i]);
  30. }
  31. }
  32. }
  33.  
  34. int binary_search_find_index(vector<int>::iterator beg, vector<int>::iterator en, int data) {
  35. vector<int>::iterator it = std::lower_bound(beg, en, data);
  36. if (it == en || *it != data) {
  37. return -1;
  38. } else {
  39. std::size_t index = std::distance(beg, it);
  40. return index;
  41. }
  42. }
  43.  
  44. //Бинарный поиск с возвратом индекса на итераторах с возвратом итератора
  45.  
  46. vector<int>::iterator binary_search_iterated(vector<int>* arr, vector<int>::iterator low, vector<int>::iterator high, int x){
  47. if (high >= low){
  48. vector<int>::iterator mid = low + (high - low)/2;
  49.  
  50. if (*mid == x){
  51. return mid;
  52. }
  53. else{
  54. if (*mid > x){
  55. return binary_search_iterated(arr, low, mid - 1, x);
  56. }
  57. else{
  58. return binary_search_iterated(arr, mid + 1, high, x);
  59. }
  60. }
  61.  
  62. }
  63. else{
  64. return low;
  65. }
  66.  
  67. }
  68.  
  69.  
  70. /*
  71. The most obvious alg
  72. Comparing all the elements in A and B with each other
  73. and inserting them in C
  74. Complexity is O(|A|*|B|)
  75. */
  76. void simple_intersection(unordered_set<int>* A, unordered_set<int>* B, unordered_set<int>* C){
  77. unordered_set<int>::const_iterator it_A, it_B;
  78. unordered_set<int>::const_iterator it_C;
  79. it_A = A->begin();
  80. it_B = B->begin();
  81. while (it_A != A->end()){
  82. while (it_B != B->end()){
  83. //cout << *it_B << ' ' << *it_A <<endl;
  84. if(*it_A == *it_B){
  85. C->insert(*it_A);
  86. }
  87. ++it_B;
  88. }
  89. it_B = B->begin();
  90. ++it_A;
  91. }
  92.  
  93.  
  94.  
  95.  
  96. }
  97.  
  98. //TODO: сделать обертку
  99. //B не должен быть мощнее A
  100. void BaezaYates_step(vector<int>* A, vector<int>* B, vector<int>::iterator A_begin, vector<int>::iterator A_end, vector<int>::iterator B_begin, vector<int>::iterator B_end, unordered_set<int> *C){
  101. if (A_end - A_begin <= 0 || B_end - B_begin <= 0){
  102. return;
  103. }
  104. vector<int>::iterator midB = B_begin + (B_end - B_begin)/2;
  105. int midBval = *midB;
  106. vector<int>::iterator midA = binary_search_iterated(A, A_begin, A_end, midBval);
  107. vector<int>::iterator a_res,b_res;
  108. if ((midA-A_begin) > (midB-B_begin)){
  109. BaezaYates_step(A,B,A_begin, midA, B_begin, midB, C);
  110. }
  111. else{
  112. BaezaYates_step(B,A,B_begin, midB, A_begin, midA, C);
  113. }
  114. if (*midA == midBval){
  115. C->insert(midBval);
  116. }
  117. if ((A_end - midA) > (B_end - midB)){
  118. BaezaYates_step(A,B,midA, A_end, midB+1, B_end, C);
  119. }
  120. else{
  121. BaezaYates_step(B,A,midB+1, B_end, midA, A_end, C);
  122. }
  123.  
  124. }
  125.  
  126.  
  127.  
  128. void GallopingIntersection(unordered_set<int>* A, unordered_set<int>* B, unordered_set<int>* C, bool isSorted = false){
  129. int low = 0;
  130. int diff, high;
  131. int k;
  132.  
  133. if (!isSorted){
  134. vector<int> A_sorted(A->begin(), A->end());
  135. vector<int> B_sorted(B->begin(), B->end()); //creating unsorted duplicates and sort them as vectors
  136. std::sort(A_sorted.begin(), A_sorted.end());
  137. std::sort(B_sorted.begin(), B_sorted.end());
  138.  
  139.  
  140.  
  141. for(int i=0; i<B_sorted.size(); ++i){ //< or <= I dunno
  142. //cout << "B[i]:" << B_sorted[i] << " ";
  143. diff = 1;
  144. while (low + diff <= A_sorted.size() && A_sorted[low + diff] <= B_sorted[i]){
  145. diff *= 2;
  146. }
  147. high = min(int(A_sorted.size()), low + diff);
  148. k = binary_search_find_index((A_sorted.begin() + low), (A_sorted.begin() + high), B_sorted[i]);
  149. if(k != -1){
  150. C->insert(B_sorted[i]);
  151. //cout << B_sorted[i];
  152. }
  153. low = k;
  154. //cout << endl;
  155.  
  156. }
  157.  
  158.  
  159. }
  160.  
  161.  
  162.  
  163. }
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171. // генератор
  172.  
  173. void lcg(vector<int>& r, int seed, int size, int a, int c, long m){
  174. if (size == 1){
  175. r.push_back((a*seed+c)%m);
  176. return;
  177. }
  178. for(int i = 0; i < size; ++i){
  179. r.push_back(0);
  180. }
  181. r[0] = seed;
  182. for(int i = 1; i < size; ++i){
  183. r[i] = (a*r[i-1]+c)%m;
  184. }
  185. r.erase(r.begin());
  186. }
  187.  
  188.  
  189.  
  190. void generate(int seed, long size, double a2b, double i2u, vector<int> & a, vector<int>& b){
  191. //hardcoded consts for lcg generator
  192. //a = 50001
  193. //c = 49999
  194. //m = 2500000000
  195. int inter = int(size*i2u);
  196. int a_size = int(a2b*size*(1-i2u)/(a2b+1))+inter;
  197. int b_size = int(size*(1-i2u)/(a2b+1))+inter;
  198. lcg(a, seed, a_size, 50001, 49999, 2500000000);
  199. lcg(b, a[a_size - inter],b_size, 50001, 49999, 2500000000);
  200. }
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210. //тестер
  211.  
  212. int main(int argc, char* argv[]) {
  213. vector<int> a;
  214. vector<int> b;
  215.  
  216. /*
  217. 1000
  218. 2000
  219. 5000
  220. 10000
  221. 20000
  222. 50000
  223. 100000
  224. 200000
  225. 500000
  226. 1000000
  227. 2000000
  228. 5000000
  229. 10000000
  230.  
  231. */
  232. int i = 100000;
  233.  
  234. if (argc>1){
  235. i = stoi(argv[1]);
  236. }
  237.  
  238. generate(14, i, 1, 0.1, a, b);
  239.  
  240. unordered_set<int> aS(a.begin(), a.end());
  241. unordered_set<int> bS(b.begin(), b.end());
  242.  
  243.  
  244. unordered_set<int> aSN(a.begin(), a.end());
  245. unordered_set<int> bSN(b.begin(), b.end());
  246.  
  247. unordered_set<int> v_intersection;
  248. /*
  249. sort(a.begin(), a.end());
  250. sort(b.begin(), b.end());
  251.  
  252. BaezaYates_step(&a, &b, a.begin(), a.end(), b.begin(), b.end(), &v_intersection);
  253. */
  254.  
  255. unordered_set<int> res;
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262. double start_time = getCPUTime();
  263.  
  264. GallopingIntersection(&aS, &bS, &res);
  265.  
  266. double end_time = getCPUTime();
  267.  
  268. cout << res.size() << endl;
  269. // ' ' << v_intersection.size() << endl;
  270.  
  271. cout << i << ' ' << a.size() << ", " << b.size() << ", " << end_time - start_time << ",\n";
  272.  
  273. }
  274.  
Advertisement
RAW Paste Data Copied
Advertisement