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