histogram.cc

题描述的是一个旅行商要到几个城市去

#include "histogram.h"

double Histogram::findBucket (double value) {
  return (round (value / bucketWidth)) * bucketWidth;
}

void Histogram::add (Histogram *h) {
  ASSERT (bucketWidth == h->bucketWidth);
  for (map<double,int>::const_iterator iter =
	 value2count.begin();
       iter != value2count.end(); iter++) {
    add (iter->first, iter->second, false);
  }
  size += h->size;
  sum += h->sum;
}

void Histogram::add (double value, int count, bool doCoerce) {
  // to get more exact mean, remember values before we coerce them
  sum += (value * count);
  if (doCoerce) {
    value = findBucket (value);
  }

  map<double,int>::iterator iter = value2count.find(value);
  if (iter == value2count.end()) {
    value2count.insert (pair<double,int>(value,count));
    values.push_back (value);
  } else {
    iter->second += count;
  }
  size += count;
}

double Histogram::mean () {
  if (size == 0) return 0.;
  return (sum / size);
}

double Histogram::percentile (double pct) {
  sort (values.begin(), values.end());
  int currentIndex = 0;
  int targetIndex = int(size * pct);
  double currentValue;
  if (size == 0) return 0;

  for (map<double,int>::const_iterator iter =
	 value2count.begin();
       iter != value2count.end(); iter++) {
    currentIndex += iter->second;
    currentValue = iter->first;

    if (currentIndex >= targetIndex)
      break;
  }
  return currentValue;
}
  
ostream& operator << (ostream& os, Histogram* h) 
{
  for (map<double,int>::const_iterator iter =
	 h->value2count.begin();
       iter != h->value2count.end(); iter++) {
    os << iter->first << " -> " << iter->second << "\n";
  }
  return os;
}

/*
int main () {
  printf ("histogram driver\n");
  Histogram *h = new Histogram (2.);
  h->add (2);
  h->add (3);
  h->add (3.2);
  h->add (1.8);
  h->add (10);
  h->add (11);
  h->add (9);

  cout << h << endl;
  cout << "mean " << h->mean() << endl;
  cout << "p 0 " << h->percentile (0) << endl;
  cout << "p .1 " << h->percentile (.1) << endl;
  cout << "p .5 " << h->percentile (.5) << endl;
  cout << "p .9 " << h->percentile (.9) << endl;
  cout << "p 1 " << h->percentile (1) << endl;

}
*/