fork(3) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rdrEnt
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!