# 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.