iof-bird-daemon / misc / ips.c @ ae80a2de
History | View | Annotate | Download (2.11 KB)
1 |
#include <stdio.h> |
---|---|
2 |
#include <math.h> |
3 |
#include <unistd.h> |
4 |
#include <stdlib.h> |
5 |
|
6 |
int h[65536]; |
7 |
|
8 |
/*
|
9 |
* Probability analysis of hashing function:
|
10 |
*
|
11 |
* Let n be number of items and k number of boxes. For uniform distribution
|
12 |
* we get:
|
13 |
*
|
14 |
* Expected value of "item i is in given box": Xi = 1/k
|
15 |
* Expected number of items in given box: a = EX = E(sum Xi) = sum E(Xi) = n/k
|
16 |
* Expected square value: E(X^2) = E((sum Xi)^2) = E((sum_i Xi^2) + (sum_i,j i<>j XiXj)) =
|
17 |
* = sum_i E(Xi^2) + sum_i,j i<>j E(XiXj) =
|
18 |
* = sum_i E(Xi) [Xi is binary] + sum_i,j i<>j E(XiXj) [those are independent] =
|
19 |
* = n/k + n*(n-1)/k^2
|
20 |
* Variance: var X = E(X^2) - (EX)^2 = n/k + n*(n-1)/k^2 - n^2/k^2 =
|
21 |
* = n/k - n/k^2 = a * (1-1/k)
|
22 |
* Probability of fixed box being zero: Pz = ((k-1)/k)^n = (1-1/k)^n = (1-1/k)^(ak) =
|
23 |
* = ((1-1/k)^k)^a which we can approximate by e^-a.
|
24 |
*/
|
25 |
|
26 |
uint hf(uint n) |
27 |
{ |
28 |
#if 0
|
29 |
n = (n ^ (n >> 16)) & 0xffff;
|
30 |
n = (n ^ (n << 8)) & 0xffff;
|
31 |
#elif 1
|
32 |
n = (n >> 16) ^ n;
|
33 |
n = (n ^ (n << 10)) & 0xffff; |
34 |
#elif 0 |
35 |
n = (n >> 16) ^ n;
|
36 |
n *= 259309;
|
37 |
#elif 0 |
38 |
n ^= (n >> 20);
|
39 |
n ^= (n >> 10);
|
40 |
n ^= (n >> 5);
|
41 |
#elif 0 |
42 |
n = (n * 259309) + ((n >> 16) * 123479); |
43 |
#else
|
44 |
return random();
|
45 |
#endif
|
46 |
return n;
|
47 |
} |
48 |
|
49 |
int
|
50 |
main(int argc, char **argv) |
51 |
{ |
52 |
int cnt=0; |
53 |
int i;
|
54 |
|
55 |
int bits = atol(argv[1]); |
56 |
int z = 1 << bits; |
57 |
int max = atol(argv[2]); |
58 |
|
59 |
while (max--)
|
60 |
{ |
61 |
uint i, e; |
62 |
if (scanf("%x/%d", &i, &e) != 2) |
63 |
if (feof(stdin))
|
64 |
break;
|
65 |
else
|
66 |
fprintf(stderr, "BUGGG\n");
|
67 |
// i >>= (32-e);
|
68 |
// i |= (i >> e);
|
69 |
cnt++; |
70 |
h[(hf(i) >> 1*(16 - bits)) & (z-1)]++; |
71 |
} |
72 |
// printf(">>> %d addresses\n", cnt);
|
73 |
#if 0
|
74 |
for(i=0; i<z; i++)
|
75 |
printf("%d\t%d\n", i, h[i]);
|
76 |
#else
|
77 |
{ |
78 |
int min=cnt, max=0, zer=0; |
79 |
double delta=0; |
80 |
double avg = (double) cnt / z; |
81 |
double exdelta = avg*(1-1/(double)z); |
82 |
double exzer = exp(-avg);
|
83 |
for(i=0; i<z; i++) { |
84 |
if (h[i] < min) min=h[i];
|
85 |
if (h[i] > max) max=h[i];
|
86 |
delta += (h[i] - avg) * (h[i] - avg); |
87 |
if (!h[i]) zer++;
|
88 |
} |
89 |
printf("size=%5d, min=%d, max=%2d, delta=%-7.6g (%-7.6g), avg=%-5.3g, zero=%g%% (%g%%)\n", z, min, max, delta/z, exdelta, avg, zer/(double)z*100, exzer*100); |
90 |
} |
91 |
#endif
|
92 |
|
93 |
return 0; |
94 |
} |