QTimingAnalyzer.cc

Go to the documentation of this file.

/*
 * Author: Adam Bryant (adam_bryant@berkeley.edu)
 *
 * Class: QTimingAnalyzer
 *
 */
 
#include "QTimingAnalyzer.hh"
#include <algorithm>
#include <cmath>
#include <gsl/gsl_cdf.h>
 
using std::fabs;
using std::lower_bound;
using std::max_element;
using std::min;
using std::min_element;
using std::pow;
using std::vector;
 
QTimingAnalyzer::QTimingAnalyzer()
    : fNeedsSort(true), fPeriod(1.0), fTolerance(1.0)
{
}
 
QTimingAnalyzer::~QTimingAnalyzer()
{
}
 
void QTimingAnalyzer::ComputeGoodnessThreshold(const double falseRate)
{
    // event rate
    double rate = 0;
    
    // maximum time
    double maximum = 0;
    
    if (fValues.size() != 0) {
        maximum = *( max_element(fValues.begin(), fValues.end()) );
 
        if (maximum > 0) {
            rate = fValues.size() / maximum;
        }
    }
    
    // probability of event within +/- tolerance
    double p = 1.0 - exp(-rate * (2.0 * fTolerance));
    
    // number of trials
    unsigned int n
        = fPeriod > 0
        ? (unsigned int) (maximum / fPeriod)
        : 0;
    
    unsigned int k = 0;
    while( 1.0 - pow(gsl_cdf_binomial_P(k, p, n), 1.0 + fAdjustments.size())
           > falseRate ) {
        ++k;
    }
    
    fGoodnessThreshold = k;
}
 
double QTimingAnalyzer::DistanceToClosestElement(const double value,
                                                 double& closestValue)
{
    double distance = 0;
 
    // vector should be sorted ascending
    if (fNeedsSort) {
        sort(fValues.begin(), fValues.end());
        fNeedsSort = false;
    }
    
    // Perform binary search for nearest elements
    vector<double>::const_iterator position
        = lower_bound(fValues.begin(), fValues.end(), value);
        // returns an iterator to the first position in which 'value' can be
        // inserted while preserving the ordering
    
    if (position == fValues.begin()) {
        distance = fValues.front() - value;
        closestValue = fValues.front();
    }
    else if (position == fValues.end()) {
        distance = value - fValues.back();
        closestValue = fValues.back();
    }
    else {
        double distanceBelow = value - *(position - 1);
        double distanceAbove = *position - value;
        distance = min(distanceBelow, distanceAbove);
        if (distanceBelow < distanceAbove) {
            closestValue = *(position - 1);
        }
        else {
            closestValue = *position;
        }
    }
    
    return distance;
}
 
void QTimingAnalyzer::FindPeriod(const double uncertainty,
                                 const double stepSize)
{
    const double oldPeriod = fPeriod;
    double bestPeriod = oldPeriod;
 
    unsigned int bestTotalGoodness = GetTotalGoodness();
    
    int steps = 1;
    while ( fabs(steps * stepSize) < uncertainty ) {
        
        fPeriod = oldPeriod + steps * stepSize;
        unsigned int totalGoodness = GetTotalGoodness();
        
        if (totalGoodness > bestTotalGoodness) {
            bestTotalGoodness = totalGoodness;
            bestPeriod = fPeriod;
        }
        
        steps *= -1;
        if (steps >= 0) {
            ++steps;
        }
    }
    
    fPeriod = bestPeriod;
}
 
unsigned int QTimingAnalyzer::GetBestGoodness()
{
    unsigned int bestGoodness = 0;
    
    for (vector<double>::const_iterator valueIter = fValues.begin();
         valueIter != fValues.end();
         ++valueIter) {
    
        unsigned int goodness = GetGoodnessParameter(*valueIter);
        
        if (goodness > bestGoodness) {
            bestGoodness = goodness;
        }
        
    }
    
    return bestGoodness;
}
 
unsigned int QTimingAnalyzer::GetGoodness(const double value)
{
    unsigned int goodness = GetGoodnessParameter(value);
    
    for (vector<double>::const_iterator adjustmentIter = fAdjustments.begin();
         adjustmentIter != fAdjustments.end();
         ++adjustmentIter) {
        
        double adjustedValue = value + *adjustmentIter;
        unsigned int goodnessWithAdjustment
            = GetGoodnessParameter(adjustedValue);
        
        if (goodnessWithAdjustment > goodness) {
            goodness = goodnessWithAdjustment;
        }
        
    }
    
    return goodness;
}
 
unsigned int QTimingAnalyzer::GetGoodnessParameter(const double value)
{
    // Initialize the goodness parameter
    unsigned int goodness = 0;
    
    if (fValues.size() != 0) {
        
        double maximum = *( max_element(fValues.begin(), fValues.end()) );
        double minimum = *( min_element(fValues.begin(), fValues.end()) );
        
        double closestVal = 0;
        
        for (double val = value;
             val < maximum + fTolerance;
             val += fPeriod) {
            double distance = DistanceToClosestElement(val, closestVal);
            if (distance < fTolerance) {
                ++goodness;
            }
        }
        
        // also step backwards in time so can start with any point in vector
        for (double val = value - fPeriod;
             val > minimum - fTolerance;
             val -= fPeriod) {
            double distance = DistanceToClosestElement(val, closestVal);
            if (distance < fTolerance) {
                ++goodness;
            }
        }
    
    }
    
    return goodness;
}
 
unsigned int QTimingAnalyzer::GetTotalGoodness()
{
    unsigned int totalGoodness = 0;
    
    for (vector<double>::const_iterator valueIter = fValues.begin();
         valueIter != fValues.end();
         ++valueIter) {
        
        totalGoodness += GetGoodnessParameter(*valueIter);
        
    }
    
    return totalGoodness;
}