15976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/* 25976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * libjingle 35976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * Copyright 2011, Google Inc. 45976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * 55976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * Redistribution and use in source and binary forms, with or without 65976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * modification, are permitted provided that the following conditions are met: 75976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * 85976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * 1. Redistributions of source code must retain the above copyright notice, 95976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * this list of conditions and the following disclaimer. 105976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * 2. Redistributions in binary form must reproduce the above copyright notice, 115976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * this list of conditions and the following disclaimer in the documentation 125976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * and/or other materials provided with the distribution. 135976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * 3. The name of the author may not be used to endorse or promote products 145976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * derived from this software without specific prior written permission. 155976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * 165976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 175976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 185976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 195976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 205976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 215976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 225976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 235976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 245976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 255976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 265976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org */ 275976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 285976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#ifndef TALK_BASE_ROLLINGACCUMULATOR_H_ 295976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#define TALK_BASE_ROLLINGACCUMULATOR_H_ 305976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 315976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include <vector> 325976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 335976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "talk/base/common.h" 345976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 355976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgnamespace talk_base { 365976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 375976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// RollingAccumulator stores and reports statistics 385976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// over N most recent samples. 395976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 405976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// T is assumed to be an int, long, double or float. 415976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgtemplate<typename T> 425976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgclass RollingAccumulator { 435976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org public: 445976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org explicit RollingAccumulator(size_t max_count) 455976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org : count_(0), 465976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org next_index_(0), 475976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org sum_(0.0), 485976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org sum_2_(0.0), 495976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org samples_(max_count) { 505976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 515976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org ~RollingAccumulator() { 525976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 535976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 545976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org size_t max_count() const { 555976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return samples_.size(); 565976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 575976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 585976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org size_t count() const { 595976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return count_; 605976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 615976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 625976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org void AddSample(T sample) { 635976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (count_ == max_count()) { 645976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Remove oldest sample. 655976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org T sample_to_remove = samples_[next_index_]; 665976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org sum_ -= sample_to_remove; 675976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org sum_2_ -= sample_to_remove * sample_to_remove; 685976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } else { 695976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Increase count of samples. 705976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org ++count_; 715976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 725976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Add new sample. 735976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org samples_[next_index_] = sample; 745976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org sum_ += sample; 755976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org sum_2_ += sample * sample; 765976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Update next_index_. 775976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org next_index_ = (next_index_ + 1) % max_count(); 785976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 795976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 805976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org T ComputeSum() const { 815976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return static_cast<T>(sum_); 825976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 835976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 845976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org T ComputeMean() const { 855976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (count_ == 0) { 865976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return static_cast<T>(0); 875976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 885976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return static_cast<T>(sum_ / count_); 895976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 905976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 915976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // O(n) time complexity. 925976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Weights nth sample with weight (learning_rate)^n. Learning_rate should be 935976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // between (0.0, 1.0], otherwise the non-weighted mean is returned. 945976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org T ComputeWeightedMean(double learning_rate) const { 955976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) { 965976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return ComputeMean(); 975976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 985976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double weighted_mean = 0.0; 995976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double current_weight = 1.0; 1005976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double weight_sum = 0.0; 1015976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org const size_t max_size = max_count(); 1025976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (size_t i = 0; i < count_; ++i) { 1035976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org current_weight *= learning_rate; 1045976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org weight_sum += current_weight; 1055976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Add max_size to prevent underflow. 1065976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org size_t index = (next_index_ + max_size - i - 1) % max_size; 1075976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org weighted_mean += current_weight * samples_[index]; 1085976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1095976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return static_cast<T>(weighted_mean / weight_sum); 1105976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1115976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1125976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Compute estimated variance. Estimation is more accurate 1135976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // as the number of samples grows. 1145976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org T ComputeVariance() const { 1155976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (count_ == 0) { 1165976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return static_cast<T>(0); 1175976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1185976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Var = E[x^2] - (E[x])^2 1195976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double count_inv = 1.0 / count_; 1205976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double mean_2 = sum_2_ * count_inv; 1215976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double mean = sum_ * count_inv; 1225976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return static_cast<T>(mean_2 - (mean * mean)); 1235976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1245976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1255976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org private: 1265976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org size_t count_; 1275976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org size_t next_index_; 1285976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double sum_; // Sum(x) 1295976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org double sum_2_; // Sum(x*x) 1305976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org std::vector<T> samples_; 1315976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1325976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org DISALLOW_COPY_AND_ASSIGN(RollingAccumulator); 1335976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org}; 1345976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1355976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org} // namespace talk_base 1365976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1375976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#endif // TALK_BASE_ROLLINGACCUMULATOR_H_ 138