10e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org/* 20e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * libjingle 30e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * Copyright 2011, Google Inc. 40e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * 50e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * Redistribution and use in source and binary forms, with or without 60e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * modification, are permitted provided that the following conditions are met: 70e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * 80e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * 1. Redistributions of source code must retain the above copyright notice, 90e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * this list of conditions and the following disclaimer. 100e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * 2. Redistributions in binary form must reproduce the above copyright notice, 110e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * this list of conditions and the following disclaimer in the documentation 120e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * and/or other materials provided with the distribution. 130e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * 3. The name of the author may not be used to endorse or promote products 140e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * derived from this software without specific prior written permission. 150e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * 160e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 170e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 180e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 190e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 200e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 210e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 220e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 230e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 240e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 250e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 260e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org */ 270e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 280e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org#ifndef TALK_BASE_ROLLINGACCUMULATOR_H_ 290e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org#define TALK_BASE_ROLLINGACCUMULATOR_H_ 300e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 310e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org#include <vector> 320e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 330e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org#include "talk/base/common.h" 340e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 350e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.orgnamespace talk_base { 360e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 370e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org// RollingAccumulator stores and reports statistics 380e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org// over N most recent samples. 390e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org// 400e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org// T is assumed to be an int, long, double or float. 410e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.orgtemplate<typename T> 420e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.orgclass RollingAccumulator { 430e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org public: 440e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org explicit RollingAccumulator(size_t max_count) 457587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org : samples_(max_count) { 467587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org Reset(); 470e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 480e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org ~RollingAccumulator() { 490e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 500e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 510e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org size_t max_count() const { 520e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org return samples_.size(); 530e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 540e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 550e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org size_t count() const { 560e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org return count_; 570e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 580e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 597587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org void Reset() { 607587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org count_ = 0U; 617587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org next_index_ = 0U; 627587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org sum_ = 0.0; 637587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org sum_2_ = 0.0; 647587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_ = T(); 657587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_stale_ = false; 667587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_ = T(); 677587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_stale_ = false; 687587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 697587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org 700e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org void AddSample(T sample) { 710e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org if (count_ == max_count()) { 720e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Remove oldest sample. 730e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org T sample_to_remove = samples_[next_index_]; 740e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org sum_ -= sample_to_remove; 750e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org sum_2_ -= sample_to_remove * sample_to_remove; 767587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org if (sample_to_remove >= max_) { 777587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_stale_ = true; 787587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 797587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org if (sample_to_remove <= min_) { 807587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_stale_ = true; 817587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 820e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } else { 830e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Increase count of samples. 840e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org ++count_; 850e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 860e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Add new sample. 870e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org samples_[next_index_] = sample; 880e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org sum_ += sample; 890e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org sum_2_ += sample * sample; 907587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org if (count_ == 1 || sample >= max_) { 917587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_ = sample; 927587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_stale_ = false; 937587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 947587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org if (count_ == 1 || sample <= min_) { 957587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_ = sample; 967587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_stale_ = false; 977587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 980e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Update next_index_. 990e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org next_index_ = (next_index_ + 1) % max_count(); 1000e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1010e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1020e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org T ComputeSum() const { 1030e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org return static_cast<T>(sum_); 1040e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1050e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1067587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org double ComputeMean() const { 1070e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org if (count_ == 0) { 1087587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return 0.0; 1097587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 1107587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return sum_ / count_; 1117587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 1127587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org 1137587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org T ComputeMax() const { 1147587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org if (max_stale_) { 1157587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org ASSERT(count_ > 0 && 1167587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org "It shouldn't be possible for max_stale_ && count_ == 0"); 1177587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_ = samples_[next_index_]; 1187587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org for (size_t i = 1u; i < count_; i++) { 1197587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_ = _max(max_, samples_[(next_index_ + i) % max_count()]); 1207587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 1217587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org max_stale_ = false; 1227587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 1237587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return max_; 1247587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 1257587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org 1267587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org T ComputeMin() const { 1277587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org if (min_stale_) { 1287587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org ASSERT(count_ > 0 && 1297587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org "It shouldn't be possible for min_stale_ && count_ == 0"); 1307587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_ = samples_[next_index_]; 1317587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org for (size_t i = 1u; i < count_; i++) { 1327587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_ = _min(min_, samples_[(next_index_ + i) % max_count()]); 1337587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org } 1347587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org min_stale_ = false; 1350e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1367587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return min_; 1370e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1380e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1390e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // O(n) time complexity. 1400e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Weights nth sample with weight (learning_rate)^n. Learning_rate should be 1410e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // between (0.0, 1.0], otherwise the non-weighted mean is returned. 1427587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org double ComputeWeightedMean(double learning_rate) const { 1430e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) { 1440e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org return ComputeMean(); 1450e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1460e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org double weighted_mean = 0.0; 1470e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org double current_weight = 1.0; 1480e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org double weight_sum = 0.0; 1490e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org const size_t max_size = max_count(); 1500e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org for (size_t i = 0; i < count_; ++i) { 1510e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org current_weight *= learning_rate; 1520e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org weight_sum += current_weight; 1530e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Add max_size to prevent underflow. 1540e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org size_t index = (next_index_ + max_size - i - 1) % max_size; 1550e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org weighted_mean += current_weight * samples_[index]; 1560e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1577587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return weighted_mean / weight_sum; 1580e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1590e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1600e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Compute estimated variance. Estimation is more accurate 1610e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // as the number of samples grows. 1627587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org double ComputeVariance() const { 1630e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org if (count_ == 0) { 1647587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return 0.0; 1650e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1660e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org // Var = E[x^2] - (E[x])^2 1670e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org double count_inv = 1.0 / count_; 1680e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org double mean_2 = sum_2_ * count_inv; 1690e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org double mean = sum_ * count_inv; 1707587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org return mean_2 - (mean * mean); 1710e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org } 1720e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1730e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org private: 1740e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org size_t count_; 1750e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org size_t next_index_; 1767587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org double sum_; // Sum(x) - double to avoid overflow 1777587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org double sum_2_; // Sum(x*x) - double to avoid overflow 1787587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org mutable T max_; 1797587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org mutable bool max_stale_; 1807587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org mutable T min_; 1817587c5e0b2fb5100b52bf271370ee1369ba18690henrike@webrtc.org mutable bool min_stale_; 1820e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org std::vector<T> samples_; 1830e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1840e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org DISALLOW_COPY_AND_ASSIGN(RollingAccumulator); 1850e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org}; 1860e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1870e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org} // namespace talk_base 1880e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org 1890e118e7129884fbea117e78d6f2068139a414dbhenrike@webrtc.org#endif // TALK_BASE_ROLLINGACCUMULATOR_H_ 190