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 : count_(0), 46 next_index_(0), 47 sum_(0.0), 48 sum_2_(0.0), 49 samples_(max_count) { 50 } ~RollingAccumulator()51 ~RollingAccumulator() { 52 } 53 max_count()54 size_t max_count() const { 55 return samples_.size(); 56 } 57 count()58 size_t count() const { 59 return count_; 60 } 61 AddSample(T sample)62 void AddSample(T sample) { 63 if (count_ == max_count()) { 64 // Remove oldest sample. 65 T sample_to_remove = samples_[next_index_]; 66 sum_ -= sample_to_remove; 67 sum_2_ -= sample_to_remove * sample_to_remove; 68 } else { 69 // Increase count of samples. 70 ++count_; 71 } 72 // Add new sample. 73 samples_[next_index_] = sample; 74 sum_ += sample; 75 sum_2_ += sample * sample; 76 // Update next_index_. 77 next_index_ = (next_index_ + 1) % max_count(); 78 } 79 ComputeSum()80 T ComputeSum() const { 81 return static_cast<T>(sum_); 82 } 83 ComputeMean()84 T ComputeMean() const { 85 if (count_ == 0) { 86 return static_cast<T>(0); 87 } 88 return static_cast<T>(sum_ / count_); 89 } 90 91 // O(n) time complexity. 92 // Weights nth sample with weight (learning_rate)^n. Learning_rate should be 93 // between (0.0, 1.0], otherwise the non-weighted mean is returned. ComputeWeightedMean(double learning_rate)94 T ComputeWeightedMean(double learning_rate) const { 95 if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) { 96 return ComputeMean(); 97 } 98 double weighted_mean = 0.0; 99 double current_weight = 1.0; 100 double weight_sum = 0.0; 101 const size_t max_size = max_count(); 102 for (size_t i = 0; i < count_; ++i) { 103 current_weight *= learning_rate; 104 weight_sum += current_weight; 105 // Add max_size to prevent underflow. 106 size_t index = (next_index_ + max_size - i - 1) % max_size; 107 weighted_mean += current_weight * samples_[index]; 108 } 109 return static_cast<T>(weighted_mean / weight_sum); 110 } 111 112 // Compute estimated variance. Estimation is more accurate 113 // as the number of samples grows. ComputeVariance()114 T ComputeVariance() const { 115 if (count_ == 0) { 116 return static_cast<T>(0); 117 } 118 // Var = E[x^2] - (E[x])^2 119 double count_inv = 1.0 / count_; 120 double mean_2 = sum_2_ * count_inv; 121 double mean = sum_ * count_inv; 122 return static_cast<T>(mean_2 - (mean * mean)); 123 } 124 125 private: 126 size_t count_; 127 size_t next_index_; 128 double sum_; // Sum(x) 129 double sum_2_; // Sum(x*x) 130 std::vector<T> samples_; 131 132 DISALLOW_COPY_AND_ASSIGN(RollingAccumulator); 133 }; 134 135 } // namespace talk_base 136 137 #endif // TALK_BASE_ROLLINGACCUMULATOR_H_ 138