| #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); |
| } |
| } |
| |
| //----------------------------------------------------------------------------- |