Line data Source code
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/checks.h"
18 : #include "webrtc/base/common.h"
19 : #include "webrtc/base/constructormagic.h"
20 :
21 : namespace rtc {
22 :
23 : // RollingAccumulator stores and reports statistics
24 : // over N most recent samples.
25 : //
26 : // T is assumed to be an int, long, double or float.
27 : template<typename T>
28 : class RollingAccumulator {
29 : public:
30 0 : explicit RollingAccumulator(size_t max_count)
31 0 : : samples_(max_count) {
32 0 : Reset();
33 0 : }
34 0 : ~RollingAccumulator() {
35 0 : }
36 :
37 0 : size_t max_count() const {
38 0 : return samples_.size();
39 : }
40 :
41 : size_t count() const {
42 : return count_;
43 : }
44 :
45 0 : void Reset() {
46 0 : count_ = 0U;
47 0 : next_index_ = 0U;
48 0 : sum_ = 0.0;
49 0 : sum_2_ = 0.0;
50 0 : max_ = T();
51 0 : max_stale_ = false;
52 0 : min_ = T();
53 0 : min_stale_ = false;
54 0 : }
55 :
56 0 : void AddSample(T sample) {
57 0 : if (count_ == max_count()) {
58 : // Remove oldest sample.
59 0 : T sample_to_remove = samples_[next_index_];
60 0 : sum_ -= sample_to_remove;
61 0 : sum_2_ -= static_cast<double>(sample_to_remove) * sample_to_remove;
62 0 : if (sample_to_remove >= max_) {
63 0 : max_stale_ = true;
64 : }
65 0 : if (sample_to_remove <= min_) {
66 0 : min_stale_ = true;
67 : }
68 : } else {
69 : // Increase count of samples.
70 0 : ++count_;
71 : }
72 : // Add new sample.
73 0 : samples_[next_index_] = sample;
74 0 : sum_ += sample;
75 0 : sum_2_ += static_cast<double>(sample) * sample;
76 0 : if (count_ == 1 || sample >= max_) {
77 0 : max_ = sample;
78 0 : max_stale_ = false;
79 : }
80 0 : if (count_ == 1 || sample <= min_) {
81 0 : min_ = sample;
82 0 : min_stale_ = false;
83 : }
84 : // Update next_index_.
85 0 : next_index_ = (next_index_ + 1) % max_count();
86 0 : }
87 :
88 : T ComputeSum() const {
89 : return static_cast<T>(sum_);
90 : }
91 :
92 0 : double ComputeMean() const {
93 0 : if (count_ == 0) {
94 0 : return 0.0;
95 : }
96 0 : return sum_ / count_;
97 : }
98 :
99 : T ComputeMax() const {
100 : if (max_stale_) {
101 : RTC_DCHECK(count_ > 0) <<
102 : "It shouldn't be possible for max_stale_ && count_ == 0";
103 : max_ = samples_[next_index_];
104 : for (size_t i = 1u; i < count_; i++) {
105 : max_ = std::max(max_, samples_[(next_index_ + i) % max_count()]);
106 : }
107 : max_stale_ = false;
108 : }
109 : return max_;
110 : }
111 :
112 : T ComputeMin() const {
113 : if (min_stale_) {
114 : RTC_DCHECK(count_ > 0) <<
115 : "It shouldn't be possible for min_stale_ && count_ == 0";
116 : min_ = samples_[next_index_];
117 : for (size_t i = 1u; i < count_; i++) {
118 : min_ = std::min(min_, samples_[(next_index_ + i) % max_count()]);
119 : }
120 : min_stale_ = false;
121 : }
122 : return min_;
123 : }
124 :
125 : // O(n) time complexity.
126 : // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
127 : // between (0.0, 1.0], otherwise the non-weighted mean is returned.
128 : double ComputeWeightedMean(double learning_rate) const {
129 : if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
130 : return ComputeMean();
131 : }
132 : double weighted_mean = 0.0;
133 : double current_weight = 1.0;
134 : double weight_sum = 0.0;
135 : const size_t max_size = max_count();
136 : for (size_t i = 0; i < count_; ++i) {
137 : current_weight *= learning_rate;
138 : weight_sum += current_weight;
139 : // Add max_size to prevent underflow.
140 : size_t index = (next_index_ + max_size - i - 1) % max_size;
141 : weighted_mean += current_weight * samples_[index];
142 : }
143 : return weighted_mean / weight_sum;
144 : }
145 :
146 : // Compute estimated variance. Estimation is more accurate
147 : // as the number of samples grows.
148 : double ComputeVariance() const {
149 : if (count_ == 0) {
150 : return 0.0;
151 : }
152 : // Var = E[x^2] - (E[x])^2
153 : double count_inv = 1.0 / count_;
154 : double mean_2 = sum_2_ * count_inv;
155 : double mean = sum_ * count_inv;
156 : return mean_2 - (mean * mean);
157 : }
158 :
159 : private:
160 : size_t count_;
161 : size_t next_index_;
162 : double sum_; // Sum(x) - double to avoid overflow
163 : double sum_2_; // Sum(x*x) - double to avoid overflow
164 : mutable T max_;
165 : mutable bool max_stale_;
166 : mutable T min_;
167 : mutable bool min_stale_;
168 : std::vector<T> samples_;
169 :
170 : RTC_DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
171 : };
172 :
173 : } // namespace rtc
174 :
175 : #endif // WEBRTC_BASE_ROLLINGACCUMULATOR_H_
|
