1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
#include "Stats.h"
//-----------------------------------------------------------------------------
double chooseK ( int n, int k )
{
if(k > (n - k)) k = n - k;
double c = 1;
for(int i = 0; i < k; i++)
{
double t = double(n-i) / double(i+1);
c *= t;
}
return c;
}
double chooseUpToK ( int n, int k )
{
double c = 0;
for(int i = 1; i <= k; i++)
{
c += chooseK(n,i);
}
return c;
}
//-----------------------------------------------------------------------------
// Distribution "score"
// TODO - big writeup of what this score means
// Basically, we're computing a constant that says "The test distribution is as
// uniform, RMS-wise, as a random distribution restricted to (1-X)*100 percent of
// the bins. This makes for a nice uniform way to rate a distribution that isn't
// dependent on the number of bins or the number of keys
// (as long as # keys > # bins * 3 or so, otherwise random fluctuations show up
// as distribution weaknesses)
double calcScore ( const int * bins, const int bincount, const int keycount )
{
double n = bincount;
double k = keycount;
// compute rms value
double r = 0;
for(int i = 0; i < bincount; i++)
{
double b = bins[i];
r += b*b;
}
r = sqrt(r / n);
// compute fill factor
double f = (k*k - 1) / (n*r*r - k);
// rescale to (0,1) with 0 = good, 1 = bad
return 1 - (f / n);
}
//----------------------------------------------------------------------------
void plot ( double n )
{
double n2 = n * 1;
if(n2 < 0) n2 = 0;
n2 *= 100;
if(n2 > 64) n2 = 64;
int n3 = (int)n2;
if(n3 == 0)
printf(".");
else
{
char x = '0' + char(n3);
if(x > '9') x = 'X';
printf("%c",x);
}
}
//-----------------------------------------------------------------------------
|
