fork(2) download
copy 
  1.  
  2. ADT.Sequence|array(int) data = ADT.Sequence(0);
  3.  
  4. void fill(array(int) r1, array(int) r2, array(int) r3, array(int) elems) {
  5. 	if(sizeof(r1)>3) {
  6. 		return;
  7. 	}
  8. 	if(sizeof(elems)==0) {
  9. 		data->add(({r1, r2, r3}));
  10. 		return;
  11. 	}
  12. 	array(int) tmp = elems[1..];
  13. 	fill(r1+({elems[0]}), r2, r3, tmp);
  14. 	fill(r1, r2+({elems[0]}), r3, tmp);
  15. 	fill(r1, r2, r3+({elems[0]}), tmp);
  16. }
  17.  
  18. int to_bin(array(array(int)) rows) {
  19. 	int ret = 0;
  20. 	foreach(rows, array(int) r) {
  21. 		ret = ret << 5;
  22. 		foreach(r, int c) {
  23. 			ret = ret | (1<<c);	
  24. 		}
  25. 	}
  26. 	return ret;
  27. }
  28.  
  29. int compatible(array(int) a, array(int) b) {
  30. 	for(int i = 0; i < min(sizeof(a), sizeof(b)); ++i) {
  31. 		if(a[i]+b[i] > 1) {
  32. 			return 0;
  33. 		}
  34. 	}
  35. 	return 1;
  36. }
  37.  
  38. array(int|array(int)) hash_func(array(int) data, void|int pow2) {
  39. 	int size = max((int)ceil(sqrt(max(@data))), sizeof(data));
  40. 	if(pow2) {
  41. 		size = 1<<(int)ceil(Math.log2(size));	
  42. 	}
  43. 	array(int) st;
  44. 	array(int) o;
  45.  
  46. 	int fitted;
  47. 	do {
  48. 		fitted = 1;
  49. 		array(int) rowcounts = ({0})*size;
  50. 		o = indices(rowcounts);
  51. 		array(array(int)) table = ({({0})*size})*size;
  52. 		table = map(table, lambda(array arr) {return arr+({});});	
  53. 		foreach(data, int i) {
  54. 			table[i/size][i%size] = 1;
  55. 			rowcounts[i/size] += 1;
  56. 		}
  57. 		sort(rowcounts, table, o);
  58. 		array(int) ht = ({0})*size;
  59. 		st = ({0})*size;
  60. 		for(int i = size-1; i >= 0; --i) {
  61. 			while(st[i] < size && compatible(ht, table[i])==0){
  62. 				table[i] = Array.unshift(@reverse(Array.pop(table[i])));
  63. 				++st[i];
  64. 			}
  65. 			if(st[i] == size) {
  66. 				fitted = 0;
  67. 				if(pow2) {
  68. 					size <<= 1;
  69. 				} 
  70. 				else {
  71. 					++size;
  72. 				}
  73. 				break;
  74. 			}
  75. 			for(int j = 0; j < size; ++j) {
  76. 				ht[j] += table[i][j];
  77. 			}
  78. 		}
  79. 	} while(fitted == 0);
  80. 	sort(o, st);
  81. 	return ({size, st});
  82. }
  83.  
  84. void|string size(string prefix, void|int sz) {
  85. 	if(sz) {
  86. 		write("#define %sSIZE %d\n", prefix, sz);
  87. 	}
  88. 	else {
  89. 		return prefix+"SIZE";
  90. 	}
  91. }
  92.  
  93. void table(string prefix, string|int index) {
  94. 	write("%sTABLE[%s]", prefix, ""+index);
  95. }
  96.  
  97. void shift(string prefix, string|int index, void|array(int) st) {
  98. 	if(st) {
  99. 		write("int ");
  100. 	}
  101. 	write("%sSHIFT[%s]", prefix, ""+index);
  102. 	if(st) {
  103. 		write(" = {%d", st[0]);
  104. 		foreach(st[1..], int s) {
  105. 			write(", %d", s);
  106. 		}
  107. 		write("};\n");
  108. 	}
  109. }
  110.  
  111. void key(string prefix, string|int index) {
  112. 	write("(((%s)+", ""+index);
  113. 	shift(prefix, index);
  114. 	write(")%%%s)", size(prefix));
  115. }
  116.  
  117. void output_c(string prefix, int sz, array(int) st) {
  118. 	size(prefix, sz);
  119. 	shift(prefix, size(prefix), st);
  120. 	write("int ");
  121. 	table(prefix, size(prefix));
  122. 	write(";\n#define %skey(index) ", prefix);
  123. 	key(prefix, "index");
  124. 	write("\n#define %slookup(index) ", prefix);
  125. 	table(prefix, prefix+"key(index)");
  126. 	write("\n");
  127. }
  128.  
  129. int main() {
  130. 	fill(({}), ({}), ({}), ({0,1,2,3,4}));
  131. 	data = map(data, to_bin);
  132. 	array hf = hash_func(data);
  133. 	output_c("HT_", hf[0], hf[1]);
  134. }
Success #stdin #stdout 0.06s 32904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#define HT_SIZE 232
int HT_SHIFT[HT_SIZE] = {0, 0, 0, 0, 1, 0, 12, 6, 10, 4, 3, 0, 0, 15, 1, 51, 62, 34, 4, 4, 0, 4, 78, 11, 37, 6, 13, 12, 22, 0, 0, 135, 118, 71, 54, 0, 10, 1, 0, 10, 7, 7, 2, 0, 2, 0, 3, 63, 6, 9, 18, 5, 0, 0, 0, 0, 0, 1, 0, 1, 0, 6, 6, 0, 3, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 8, 19, 10, 0, 0, 0, 0, 0, 0, 25, 7, 9, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 5, 0, 0, 2, 10, 0, 0, 0, 0, 0, 0, 0, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int HT_TABLE[HT_SIZE];
#define HT_key(index) (((index)+HT_SHIFT[index])%HT_SIZE)
#define HT_lookup(index) HT_TABLE[HT_key(index)]
https://ideone.com/IhJr3o
language:
Pike (pike 8.0)
created:
6 years ago
visibility:
secret

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!