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