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