Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(315)

Side by Side Diff: webrtc/base/rollingaccumulator.h

Issue 2877023002: Move webrtc/{base => rtc_base} (Closed)
Patch Set: update presubmit.py and DEPS include rules Created 3 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « webrtc/base/refcountedobject_unittest.cc ('k') | webrtc/base/rollingaccumulator_unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2011 The WebRTC Project Authors. All rights reserved. 2 * Copyright 2011 The WebRTC Project Authors. All rights reserved.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license 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 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 6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may 7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree. 8 * be found in the AUTHORS file in the root of the source tree.
9 */ 9 */
10 10
11 #ifndef WEBRTC_BASE_ROLLINGACCUMULATOR_H_ 11 #ifndef WEBRTC_BASE_ROLLINGACCUMULATOR_H_
12 #define WEBRTC_BASE_ROLLINGACCUMULATOR_H_ 12 #define WEBRTC_BASE_ROLLINGACCUMULATOR_H_
13 13
14 #include <algorithm>
15 #include <vector>
16 14
17 #include "webrtc/base/checks.h" 15 // This header is deprecated and is just left here temporarily during
18 #include "webrtc/base/constructormagic.h" 16 // refactoring. See https://bugs.webrtc.org/7634 for more details.
19 17 #include "webrtc/rtc_base/rollingaccumulator.h"
20 namespace rtc {
21
22 // RollingAccumulator stores and reports statistics
23 // over N most recent samples.
24 //
25 // T is assumed to be an int, long, double or float.
26 template<typename T>
27 class RollingAccumulator {
28 public:
29 explicit RollingAccumulator(size_t max_count)
30 : samples_(max_count) {
31 Reset();
32 }
33 ~RollingAccumulator() {
34 }
35
36 size_t max_count() const {
37 return samples_.size();
38 }
39
40 size_t count() const {
41 return count_;
42 }
43
44 void Reset() {
45 count_ = 0U;
46 next_index_ = 0U;
47 sum_ = 0.0;
48 sum_2_ = 0.0;
49 max_ = T();
50 max_stale_ = false;
51 min_ = T();
52 min_stale_ = false;
53 }
54
55 void AddSample(T sample) {
56 if (count_ == max_count()) {
57 // Remove oldest sample.
58 T sample_to_remove = samples_[next_index_];
59 sum_ -= sample_to_remove;
60 sum_2_ -= static_cast<double>(sample_to_remove) * sample_to_remove;
61 if (sample_to_remove >= max_) {
62 max_stale_ = true;
63 }
64 if (sample_to_remove <= min_) {
65 min_stale_ = true;
66 }
67 } else {
68 // Increase count of samples.
69 ++count_;
70 }
71 // Add new sample.
72 samples_[next_index_] = sample;
73 sum_ += sample;
74 sum_2_ += static_cast<double>(sample) * sample;
75 if (count_ == 1 || sample >= max_) {
76 max_ = sample;
77 max_stale_ = false;
78 }
79 if (count_ == 1 || sample <= min_) {
80 min_ = sample;
81 min_stale_ = false;
82 }
83 // Update next_index_.
84 next_index_ = (next_index_ + 1) % max_count();
85 }
86
87 T ComputeSum() const {
88 return static_cast<T>(sum_);
89 }
90
91 double ComputeMean() const {
92 if (count_ == 0) {
93 return 0.0;
94 }
95 return sum_ / count_;
96 }
97
98 T ComputeMax() const {
99 if (max_stale_) {
100 RTC_DCHECK(count_ > 0) <<
101 "It shouldn't be possible for max_stale_ && count_ == 0";
102 max_ = samples_[next_index_];
103 for (size_t i = 1u; i < count_; i++) {
104 max_ = std::max(max_, samples_[(next_index_ + i) % max_count()]);
105 }
106 max_stale_ = false;
107 }
108 return max_;
109 }
110
111 T ComputeMin() const {
112 if (min_stale_) {
113 RTC_DCHECK(count_ > 0) <<
114 "It shouldn't be possible for min_stale_ && count_ == 0";
115 min_ = samples_[next_index_];
116 for (size_t i = 1u; i < count_; i++) {
117 min_ = std::min(min_, samples_[(next_index_ + i) % max_count()]);
118 }
119 min_stale_ = false;
120 }
121 return min_;
122 }
123
124 // O(n) time complexity.
125 // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
126 // between (0.0, 1.0], otherwise the non-weighted mean is returned.
127 double ComputeWeightedMean(double learning_rate) const {
128 if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
129 return ComputeMean();
130 }
131 double weighted_mean = 0.0;
132 double current_weight = 1.0;
133 double weight_sum = 0.0;
134 const size_t max_size = max_count();
135 for (size_t i = 0; i < count_; ++i) {
136 current_weight *= learning_rate;
137 weight_sum += current_weight;
138 // Add max_size to prevent underflow.
139 size_t index = (next_index_ + max_size - i - 1) % max_size;
140 weighted_mean += current_weight * samples_[index];
141 }
142 return weighted_mean / weight_sum;
143 }
144
145 // Compute estimated variance. Estimation is more accurate
146 // as the number of samples grows.
147 double ComputeVariance() const {
148 if (count_ == 0) {
149 return 0.0;
150 }
151 // Var = E[x^2] - (E[x])^2
152 double count_inv = 1.0 / count_;
153 double mean_2 = sum_2_ * count_inv;
154 double mean = sum_ * count_inv;
155 return mean_2 - (mean * mean);
156 }
157
158 private:
159 size_t count_;
160 size_t next_index_;
161 double sum_; // Sum(x) - double to avoid overflow
162 double sum_2_; // Sum(x*x) - double to avoid overflow
163 mutable T max_;
164 mutable bool max_stale_;
165 mutable T min_;
166 mutable bool min_stale_;
167 std::vector<T> samples_;
168
169 RTC_DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
170 };
171
172 } // namespace rtc
173 18
174 #endif // WEBRTC_BASE_ROLLINGACCUMULATOR_H_ 19 #endif // WEBRTC_BASE_ROLLINGACCUMULATOR_H_
OLDNEW
« no previous file with comments | « webrtc/base/refcountedobject_unittest.cc ('k') | webrtc/base/rollingaccumulator_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698