smhasher/Stats.cpp

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

//-----------------------------------------------------------------------------