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