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