fork download
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <bitset>
  5. #include <set>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. #pragma comment(linker, "/STACK:1677721600")
  11.  
  12. class CuckooHashTable {//set like - no duplicates
  13. public:
  14. static const int MAXP = 666013, MULT = 10;
  15. private:
  16. set<int> stash;
  17. static const int D = 2;
  18. int A[D];
  19. int B[D];
  20. int kt[MULT];
  21. int T[MULT][MAXP];
  22. bitset<MAXP> u[MULT];
  23. int perm[2][32];
  24. int hash(int idx, int x) {
  25. int xnou = 0;
  26. for(int i = 0; i < 32; i++) {
  27. xnou = (xnou << 1) + ((x & (1 << perm[idx][31 - i])) >> perm[idx][31 - i]);
  28. }
  29. xnou = ((xnou % MAXP) + MAXP) % MAXP;
  30. return xnou;
  31. }
  32. bool insert_in_free(int i, int x, int h1, int h2) {
  33. if(!u[i][h1]) {
  34. u[i][h1].flip();
  35. T[i][h1] = x;
  36. return true;
  37. }
  38. else if(!u[i][h2]){
  39. u[i][h2].flip();
  40. T[i][h2] = x;
  41. return true;
  42. }
  43. return false;
  44. }
  45. public:
  46. CuckooHashTable() {
  47. srand(time(NULL));
  48. bool must_continue = true;
  49. for(int i = 0; i < MULT; i++) {
  50. kt[i] = 0;
  51. }
  52. while(must_continue) {
  53. for(int i = 0; i < D; i++) {
  54. A[i] = rand() % 100;
  55. B[i] = rand() % (i == 0? 100 : 10000);
  56. }
  57. for(int i = 0; i < D && must_continue; i++) {
  58. for(int j = i + 1; j < D && must_continue; j++) {
  59. if(A[i] != A[j] || B[i] != B[j]) {
  60. must_continue = false;
  61. }
  62. }
  63. }
  64. }
  65. for(int i = 0; i < 32; i++) {
  66. perm[0][i] = i;
  67. perm[1][i] = i;
  68. }
  69. random_shuffle(perm[0], perm[0] + 32);
  70. random_shuffle(perm[1], perm[1] + 32);
  71. }
  72. void clearStash() {
  73. stash.clear();
  74. }
  75. int stashSize() {
  76. return stash.size();
  77. }
  78. int getFill(int y) {
  79. return kt[y];
  80. }
  81. int dfs(int i, int x, int h, int depth) {
  82. if(!u[i][h]) { u[i][h] = true; T[i][h] = x; return true;}
  83. if(depth > 0) {
  84. int hf = hash(0, T[i][h]);
  85. hf = (hf == h ? hash(1, T[i][h]) : hf);
  86. if(dfs(i, T[i][h], hf, depth - 1)) {
  87. T[i][h] = x;
  88. return true;
  89. }
  90. }
  91. return false;
  92. }
  93. void insert(int x) {//works with D = 2
  94. if(has(x)) return;
  95. int h1 = hash(0, x);
  96. int h2 = hash(1, x);
  97. bool success = false;
  98. for(int i = 0; i < MULT; i++) {
  99. success = insert_in_free(i, x, h1, h2);
  100. if(!success) {
  101. success = dfs(i, x, h1, 10);
  102. }
  103. if(!success) {
  104. success = dfs(i, x, h2, 10);
  105. }
  106. if(success) {kt[i]++; return;}
  107. }
  108. if(!success) {
  109. stash.insert(x);
  110. }
  111. }
  112. bool has(int i, int x) {
  113. int h1 = hash(0, x);
  114. int h2 = hash(1, x);
  115. return ((u[i][h1] && T[i][h1] == x) || (u[i][h2] && T[i][h2] == x));
  116. }
  117. bool has(int x) {
  118. for(int i = 0; i < MULT; i++) {
  119. if(has(i, x)) return true;
  120. }
  121. return (stash.find(x) != stash.end());
  122. }
  123. void erase(int i, int x) {
  124. int h1 = hash(0, x);
  125. int h2 = hash(1, x);
  126. if(u[i][h1] && T[i][h1] == x) {
  127. u[i][h1] = false;
  128. }
  129. if(u[i][h2] && T[i][h2] == x) {
  130. u[i][h2] = false;
  131. }
  132. }
  133. };
  134.  
  135. CuckooHashTable T;
  136.  
  137.  
  138. int a[CuckooHashTable::MULT * CuckooHashTable::MAXP];
  139.  
  140. void generare(){
  141. int x;
  142. srand(time(0));
  143. for(int i = 0; i < CuckooHashTable::MULT * CuckooHashTable::MAXP; i++) {
  144. do{
  145. x = rand() * (1 << 15) + rand();
  146. } while(x < 0/* || T.has(x)*/);//!!!!!!!!!!!!!!!!!!!!
  147. a[i] = x;
  148. }
  149. }
  150.  
  151. void insertInCuckoo() {
  152. for(int i = 0; i < CuckooHashTable::MULT * CuckooHashTable::MAXP; i++) {
  153. T.insert(a[i]);
  154. }
  155. }
  156.  
  157. set<int> s;
  158.  
  159. void insertInSet() {
  160. cout << s.max_size() << endl;
  161. for(int i = 0; i < CuckooHashTable::MULT * CuckooHashTable::MAXP; i++) {
  162. s.insert(a[i]);
  163. }
  164. }
  165.  
  166. int main() {
  167. cout << clock() << endl;
  168. generare();
  169. cout << clock() << endl;
  170. insertInSet();
  171. cout << clock() << endl;
  172. insertInCuckoo();
  173. cout << clock() << endl << endl;
  174. cout <<( T.MULT * T.MAXP - T.stashSize()) * 100.0 / (T.MAXP * T.MULT) << endl << endl;
  175. for(int i = 0; i < T.MULT; i++) {
  176. cout <<(T.getFill(i) * 100.00 / T.MAXP) << endl;
  177. }
  178. T.clearStash();
  179. s.clear();
  180. return 0;
  181. }
  182.  
  183.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout

Standard output is empty