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:
RollingAccumulator(size_t max_count)28   explicit RollingAccumulator(size_t max_count)
29     : samples_(max_count) {
30     Reset();
31   }
~RollingAccumulator()32   ~RollingAccumulator() {
33   }
34 
max_count()35   size_t max_count() const {
36     return samples_.size();
37   }
38 
count()39   size_t count() const {
40     return count_;
41   }
42 
Reset()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 
AddSample(T sample)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 
ComputeSum()86   T ComputeSum() const {
87     return static_cast<T>(sum_);
88   }
89 
ComputeMean()90   double ComputeMean() const {
91     if (count_ == 0) {
92       return 0.0;
93     }
94     return sum_ / count_;
95   }
96 
ComputeMax()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 
ComputeMin()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.
ComputeWeightedMean(double learning_rate)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.
ComputeVariance()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