1 /* 2 * libjingle 3 * Copyright 2011, Google Inc. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright notice, 9 * this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright notice, 11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * 3. The name of the author may not be used to endorse or promote products 14 * derived from this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 18 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 19 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 24 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 25 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 */ 27 28 #ifndef TALK_BASE_ROLLINGACCUMULATOR_H_ 29 #define TALK_BASE_ROLLINGACCUMULATOR_H_ 30 31 #include <vector> 32 33 #include "talk/base/common.h" 34 35 namespace talk_base { 36 37 // RollingAccumulator stores and reports statistics 38 // over N most recent samples. 39 // 40 // T is assumed to be an int, long, double or float. 41 template<typename T> 42 class RollingAccumulator { 43 public: RollingAccumulator(size_t max_count)44 explicit RollingAccumulator(size_t max_count) 45 : samples_(max_count) { 46 Reset(); 47 } ~RollingAccumulator()48 ~RollingAccumulator() { 49 } 50 max_count()51 size_t max_count() const { 52 return samples_.size(); 53 } 54 count()55 size_t count() const { 56 return count_; 57 } 58 Reset()59 void Reset() { 60 count_ = 0U; 61 next_index_ = 0U; 62 sum_ = 0.0; 63 sum_2_ = 0.0; 64 max_ = T(); 65 max_stale_ = false; 66 min_ = T(); 67 min_stale_ = false; 68 } 69 AddSample(T sample)70 void AddSample(T sample) { 71 if (count_ == max_count()) { 72 // Remove oldest sample. 73 T sample_to_remove = samples_[next_index_]; 74 sum_ -= sample_to_remove; 75 sum_2_ -= sample_to_remove * sample_to_remove; 76 if (sample_to_remove >= max_) { 77 max_stale_ = true; 78 } 79 if (sample_to_remove <= min_) { 80 min_stale_ = true; 81 } 82 } else { 83 // Increase count of samples. 84 ++count_; 85 } 86 // Add new sample. 87 samples_[next_index_] = sample; 88 sum_ += sample; 89 sum_2_ += sample * sample; 90 if (count_ == 1 || sample >= max_) { 91 max_ = sample; 92 max_stale_ = false; 93 } 94 if (count_ == 1 || sample <= min_) { 95 min_ = sample; 96 min_stale_ = false; 97 } 98 // Update next_index_. 99 next_index_ = (next_index_ + 1) % max_count(); 100 } 101 ComputeSum()102 T ComputeSum() const { 103 return static_cast<T>(sum_); 104 } 105 ComputeMean()106 double ComputeMean() const { 107 if (count_ == 0) { 108 return 0.0; 109 } 110 return sum_ / count_; 111 } 112 ComputeMax()113 T ComputeMax() const { 114 if (max_stale_) { 115 ASSERT(count_ > 0 && 116 "It shouldn't be possible for max_stale_ && count_ == 0"); 117 max_ = samples_[next_index_]; 118 for (size_t i = 1u; i < count_; i++) { 119 max_ = _max(max_, samples_[(next_index_ + i) % max_count()]); 120 } 121 max_stale_ = false; 122 } 123 return max_; 124 } 125 ComputeMin()126 T ComputeMin() const { 127 if (min_stale_) { 128 ASSERT(count_ > 0 && 129 "It shouldn't be possible for min_stale_ && count_ == 0"); 130 min_ = samples_[next_index_]; 131 for (size_t i = 1u; i < count_; i++) { 132 min_ = _min(min_, samples_[(next_index_ + i) % max_count()]); 133 } 134 min_stale_ = false; 135 } 136 return min_; 137 } 138 139 // O(n) time complexity. 140 // Weights nth sample with weight (learning_rate)^n. Learning_rate should be 141 // between (0.0, 1.0], otherwise the non-weighted mean is returned. ComputeWeightedMean(double learning_rate)142 double ComputeWeightedMean(double learning_rate) const { 143 if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) { 144 return ComputeMean(); 145 } 146 double weighted_mean = 0.0; 147 double current_weight = 1.0; 148 double weight_sum = 0.0; 149 const size_t max_size = max_count(); 150 for (size_t i = 0; i < count_; ++i) { 151 current_weight *= learning_rate; 152 weight_sum += current_weight; 153 // Add max_size to prevent underflow. 154 size_t index = (next_index_ + max_size - i - 1) % max_size; 155 weighted_mean += current_weight * samples_[index]; 156 } 157 return weighted_mean / weight_sum; 158 } 159 160 // Compute estimated variance. Estimation is more accurate 161 // as the number of samples grows. ComputeVariance()162 double ComputeVariance() const { 163 if (count_ == 0) { 164 return 0.0; 165 } 166 // Var = E[x^2] - (E[x])^2 167 double count_inv = 1.0 / count_; 168 double mean_2 = sum_2_ * count_inv; 169 double mean = sum_ * count_inv; 170 return mean_2 - (mean * mean); 171 } 172 173 private: 174 size_t count_; 175 size_t next_index_; 176 double sum_; // Sum(x) - double to avoid overflow 177 double sum_2_; // Sum(x*x) - double to avoid overflow 178 mutable T max_; 179 mutable bool max_stale_; 180 mutable T min_; 181 mutable bool min_stale_; 182 std::vector<T> samples_; 183 184 DISALLOW_COPY_AND_ASSIGN(RollingAccumulator); 185 }; 186 187 } // namespace talk_base 188 189 #endif // TALK_BASE_ROLLINGACCUMULATOR_H_ 190