Home | History | Annotate | Download | only in base 
      1 /*
      2  *  Copyright 2011 The WebRTC Project Authors. All rights reserved.
      3  *
      4  *  Use of this source code is governed by a BSD-style license
      5  *  that can be found in the LICENSE file in the root of the source
      6  *  tree. An additional intellectual property rights grant can be found
      7  *  in the file PATENTS.  All contributing project authors may
      8  *  be found in the AUTHORS file in the root of the source tree.
      9  */
     10 
     11 #ifndef WEBRTC_BASE_ROLLINGACCUMULATOR_H_
     12 #define WEBRTC_BASE_ROLLINGACCUMULATOR_H_
     13 
     14 #include <vector>
     15 
     16 #include "webrtc/base/common.h"
     17 
     18 namespace rtc {
     19 
     20 // RollingAccumulator stores and reports statistics
     21 // over N most recent samples.
     22 //
     23 // T is assumed to be an int, long, double or float.
     24 template<typename T>
     25 class RollingAccumulator {
     26  public:
     27   explicit RollingAccumulator(size_t max_count)
     28     : samples_(max_count) {
     29     Reset();
     30   }
     31   ~RollingAccumulator() {
     32   }
     33 
     34   size_t max_count() const {
     35     return samples_.size();
     36   }
     37 
     38   size_t count() const {
     39     return count_;
     40   }
     41 
     42   void Reset() {
     43     count_ = 0U;
     44     next_index_ = 0U;
     45     sum_ = 0.0;
     46     sum_2_ = 0.0;
     47     max_ = T();
     48     max_stale_ = false;
     49     min_ = T();
     50     min_stale_ = false;
     51   }
     52 
     53   void AddSample(T sample) {
     54     if (count_ == max_count()) {
     55       // Remove oldest sample.
     56       T sample_to_remove = samples_[next_index_];
     57       sum_ -= sample_to_remove;
     58       sum_2_ -= sample_to_remove * sample_to_remove;
     59       if (sample_to_remove >= max_) {
     60         max_stale_ = true;
     61       }
     62       if (sample_to_remove <= min_) {
     63         min_stale_ = true;
     64       }
     65     } else {
     66       // Increase count of samples.
     67       ++count_;
     68     }
     69     // Add new sample.
     70     samples_[next_index_] = sample;
     71     sum_ += sample;
     72     sum_2_ += sample * sample;
     73     if (count_ == 1 || sample >= max_) {
     74       max_ = sample;
     75       max_stale_ = false;
     76     }
     77     if (count_ == 1 || sample <= min_) {
     78       min_ = sample;
     79       min_stale_ = false;
     80     }
     81     // Update next_index_.
     82     next_index_ = (next_index_ + 1) % max_count();
     83   }
     84 
     85   T ComputeSum() const {
     86     return static_cast<T>(sum_);
     87   }
     88 
     89   double ComputeMean() const {
     90     if (count_ == 0) {
     91       return 0.0;
     92     }
     93     return sum_ / count_;
     94   }
     95 
     96   T ComputeMax() const {
     97     if (max_stale_) {
     98       ASSERT(count_ > 0 &&
     99           "It shouldn't be possible for max_stale_ && count_ == 0");
    100       max_ = samples_[next_index_];
    101       for (size_t i = 1u; i < count_; i++) {
    102         max_ = _max(max_, samples_[(next_index_ + i) % max_count()]);
    103       }
    104       max_stale_ = false;
    105     }
    106     return max_;
    107   }
    108 
    109   T ComputeMin() const {
    110     if (min_stale_) {
    111       ASSERT(count_ > 0 &&
    112           "It shouldn't be possible for min_stale_ && count_ == 0");
    113       min_ = samples_[next_index_];
    114       for (size_t i = 1u; i < count_; i++) {
    115         min_ = _min(min_, samples_[(next_index_ + i) % max_count()]);
    116       }
    117       min_stale_ = false;
    118     }
    119     return min_;
    120   }
    121 
    122   // O(n) time complexity.
    123   // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
    124   // between (0.0, 1.0], otherwise the non-weighted mean is returned.
    125   double ComputeWeightedMean(double learning_rate) const {
    126     if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
    127       return ComputeMean();
    128     }
    129     double weighted_mean = 0.0;
    130     double current_weight = 1.0;
    131     double weight_sum = 0.0;
    132     const size_t max_size = max_count();
    133     for (size_t i = 0; i < count_; ++i) {
    134       current_weight *= learning_rate;
    135       weight_sum += current_weight;
    136       // Add max_size to prevent underflow.
    137       size_t index = (next_index_ + max_size - i - 1) % max_size;
    138       weighted_mean += current_weight * samples_[index];
    139     }
    140     return weighted_mean / weight_sum;
    141   }
    142 
    143   // Compute estimated variance.  Estimation is more accurate
    144   // as the number of samples grows.
    145   double ComputeVariance() const {
    146     if (count_ == 0) {
    147       return 0.0;
    148     }
    149     // Var = E[x^2] - (E[x])^2
    150     double count_inv = 1.0 / count_;
    151     double mean_2 = sum_2_ * count_inv;
    152     double mean = sum_ * count_inv;
    153     return mean_2 - (mean * mean);
    154   }
    155 
    156  private:
    157   size_t count_;
    158   size_t next_index_;
    159   double sum_;    // Sum(x) - double to avoid overflow
    160   double sum_2_;  // Sum(x*x) - double to avoid overflow
    161   mutable T max_;
    162   mutable bool max_stale_;
    163   mutable T min_;
    164   mutable bool min_stale_;
    165   std::vector<T> samples_;
    166 
    167   DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
    168 };
    169 
    170 }  // namespace rtc
    171 
    172 #endif  // WEBRTC_BASE_ROLLINGACCUMULATOR_H_
    173