Statistics
| Branch: | Revision:

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
}