Home | History | Annotate | Download | only in base 
      1 /*
      2  * libjingle
      3  * Copyright 2011, Google Inc.
      4  *
      5  * Redistribution and use in source and binary forms, with or without
      6  * modification, are permitted provided that the following conditions are met:
      7  *
      8  *  1. Redistributions of source code must retain the above copyright notice,
      9  *     this list of conditions and the following disclaimer.
     10  *  2. Redistributions in binary form must reproduce the above copyright notice,
     11  *     this list of conditions and the following disclaimer in the documentation
     12  *     and/or other materials provided with the distribution.
     13  *  3. The name of the author may not be used to endorse or promote products
     14  *     derived from this software without specific prior written permission.
     15  *
     16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
     17  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
     18  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
     19  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     20  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
     22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
     23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
     24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
     25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     26  */
     27 
     28 #ifndef TALK_BASE_ROLLINGACCUMULATOR_H_
     29 #define TALK_BASE_ROLLINGACCUMULATOR_H_
     30 
     31 #include <vector>
     32 
     33 #include "talk/base/common.h"
     34 
     35 namespace talk_base {
     36 
     37 // RollingAccumulator stores and reports statistics
     38 // over N most recent samples.
     39 //
     40 // T is assumed to be an int, long, double or float.
     41 template<typename T>
     42 class RollingAccumulator {
     43  public:
     44   explicit RollingAccumulator(size_t max_count)
     45     : count_(0),
     46       next_index_(0),
     47       sum_(0.0),
     48       sum_2_(0.0),
     49       samples_(max_count) {
     50   }
     51   ~RollingAccumulator() {
     52   }
     53 
     54   size_t max_count() const {
     55     return samples_.size();
     56   }
     57 
     58   size_t count() const {
     59     return count_;
     60   }
     61 
     62   void AddSample(T sample) {
     63     if (count_ == max_count()) {
     64       // Remove oldest sample.
     65       T sample_to_remove = samples_[next_index_];
     66       sum_ -= sample_to_remove;
     67       sum_2_ -= sample_to_remove * sample_to_remove;
     68     } else {
     69       // Increase count of samples.
     70       ++count_;
     71     }
     72     // Add new sample.
     73     samples_[next_index_] = sample;
     74     sum_ += sample;
     75     sum_2_ += sample * sample;
     76     // Update next_index_.
     77     next_index_ = (next_index_ + 1) % max_count();
     78   }
     79 
     80   T ComputeSum() const {
     81     return static_cast<T>(sum_);
     82   }
     83 
     84   T ComputeMean() const {
     85     if (count_ == 0) {
     86       return static_cast<T>(0);
     87     }
     88     return static_cast<T>(sum_ / count_);
     89   }
     90 
     91   // O(n) time complexity.
     92   // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
     93   // between (0.0, 1.0], otherwise the non-weighted mean is returned.
     94   T ComputeWeightedMean(double learning_rate) const {
     95     if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
     96       return ComputeMean();
     97     }
     98     double weighted_mean = 0.0;
     99     double current_weight = 1.0;
    100     double weight_sum = 0.0;
    101     const size_t max_size = max_count();
    102     for (size_t i = 0; i < count_; ++i) {
    103       current_weight *= learning_rate;
    104       weight_sum += current_weight;
    105       // Add max_size to prevent underflow.
    106       size_t index = (next_index_ + max_size - i - 1) % max_size;
    107       weighted_mean += current_weight * samples_[index];
    108     }
    109     return static_cast<T>(weighted_mean / weight_sum);
    110   }
    111 
    112   // Compute estimated variance.  Estimation is more accurate
    113   // as the number of samples grows.
    114   T ComputeVariance() const {
    115     if (count_ == 0) {
    116       return static_cast<T>(0);
    117     }
    118     // Var = E[x^2] - (E[x])^2
    119     double count_inv = 1.0 / count_;
    120     double mean_2 = sum_2_ * count_inv;
    121     double mean = sum_ * count_inv;
    122     return static_cast<T>(mean_2 - (mean * mean));
    123   }
    124 
    125  private:
    126   size_t count_;
    127   size_t next_index_;
    128   double sum_;    // Sum(x)
    129   double sum_2_;  // Sum(x*x)
    130   std::vector<T> samples_;
    131 
    132   DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
    133 };
    134 
    135 }  // namespace talk_base
    136 
    137 #endif  // TALK_BASE_ROLLINGACCUMULATOR_H_
    138