Home | History | Annotate | Download | only in base 
      1 <!DOCTYPE html>
      2 <!--
      3 Copyright 2016 The Chromium Authors. All rights reserved.
      4 Use of this source code is governed by a BSD-style license that can be
      5 found in the LICENSE file.
      6 -->
      7 
      8 <link rel="import" href="/tracing/base/base.html">
      9 
     10 <script>
     11 'use strict';
     12 
     13 tr.exportTo('tr.b', function() {
     14   /***
     15   * An object of this class computes basic statistics online in O(1).
     16   * Usage:
     17   * 1. Create an instance.
     18   * 2. Add numbers using the |add| method.
     19   * 3. Query statistics.
     20   * 4. Repeat from step 2.
     21   */
     22   class RunningStatistics {
     23     constructor() {
     24       this.mean_ = 0;
     25       this.count_ = 0;
     26       this.max_ = -Infinity;
     27       this.min_ = Infinity;
     28       this.sum_ = 0;
     29       this.variance_ = 0;
     30 
     31       // Mean of logarithms of absolute values of samples, or undefined if any
     32       // samples were <= 0.
     33       this.meanlogs_ = 0;
     34     }
     35 
     36     get count() {
     37       return this.count_;
     38     }
     39 
     40     get geometricMean() {
     41       if (this.meanlogs_ === undefined)
     42         return 0;
     43       return Math.exp(this.meanlogs_);
     44     }
     45 
     46     get mean() {
     47       if (this.count_ == 0)
     48         return undefined;
     49       return this.mean_;
     50     }
     51 
     52     get max() {
     53       return this.max_;
     54     }
     55 
     56     get min() {
     57       return this.min_;
     58     }
     59 
     60     get sum() {
     61       return this.sum_;
     62     }
     63 
     64     get variance() {
     65       if (this.count_ == 0)
     66         return undefined;
     67       if (this.count_ == 1)
     68         return 0;
     69       return this.variance_ / (this.count_ - 1);
     70     }
     71 
     72     get stddev() {
     73       if (this.count_ == 0)
     74         return undefined;
     75       return Math.sqrt(this.variance);
     76     }
     77 
     78     add(x) {
     79       this.count_++;
     80       this.max_ = Math.max(this.max_, x);
     81       this.min_ = Math.min(this.min_, x);
     82       this.sum_ += x;
     83 
     84       // The geometric mean is computed using the arithmetic mean of logarithms.
     85       if (x <= 0)
     86         this.meanlogs_ = undefined;
     87       else if (this.meanlogs_ !== undefined)
     88         this.meanlogs_ += (Math.log(Math.abs(x)) - this.meanlogs_) / this.count;
     89 
     90       // The following uses Welford's algorithm for computing running mean
     91       // and variance. See http://www.johndcook.com/blog/standard_deviation.
     92       if (this.count_ === 1) {
     93         this.mean_ = x;
     94         this.variance_ = 0;
     95       } else {
     96         var oldMean = this.mean_;
     97         var oldVariance = this.variance_;
     98         // Using the 2nd formula for updating the mean yields better precision
     99         // but it doesn't work for the case oldMean is Infinity. Hence we handle
    100         // that case separately.
    101         if (oldMean === Infinity || oldMean === -Infinity) {
    102           this.mean_ = this.sum_ / this.count_;
    103         } else {
    104           this.mean_ = oldMean + (x - oldMean) / this.count_;
    105         }
    106         this.variance_ = oldVariance + (x - oldMean) * (x - this.mean_);
    107       }
    108     }
    109 
    110     merge(other) {
    111       var result = new RunningStatistics();
    112       result.count_ = this.count_ + other.count_;
    113       result.sum_ = this.sum_ + other.sum_;
    114       result.min_ = Math.min(this.min_, other.min_);
    115       result.max_ = Math.max(this.max_, other.max_);
    116       if (result.count === 0) {
    117         result.mean_ = 0;
    118         result.variance_ = 0;
    119         result.meanlogs_ = 0;
    120       } else {
    121         // Combine the mean and the variance using the formulas from
    122         // https://goo.gl/ddcAep.
    123         result.mean_ = result.sum / result.count;
    124         var deltaMean = (this.mean || 0) - (other.mean || 0);
    125         result.variance_ = this.variance_ + other.variance_ +
    126           (this.count * other.count * deltaMean * deltaMean / result.count);
    127 
    128         // Merge the arithmetic means of logarithms of absolute values of
    129         // samples, weighted by counts.
    130         if (this.meanlogs_ === undefined || other.meanlogs_ === undefined) {
    131           result.meanlogs_ = undefined;
    132         } else {
    133           result.meanlogs_ = (this.count * this.meanlogs_ +
    134               other.count * other.meanlogs_) / result.count;
    135         }
    136       }
    137       return result;
    138     }
    139 
    140     asDict() {
    141       return {
    142         mean: this.mean,
    143         meanlogs: this.meanlogs_,
    144         count: this.count,
    145         max: this.max,
    146         min: this.min,
    147         sum: this.sum,
    148         variance: this.variance_
    149       };
    150     }
    151 
    152     static fromDict(d) {
    153       var result = new RunningStatistics();
    154       result.mean_ = d.mean;
    155       result.count_ = d.count;
    156       result.max_ = d.max;
    157       result.min_ = d.min;
    158       result.sum_ = d.sum;
    159       result.variance_ = d.variance;
    160       result.meanlogs_ = d.meanlogs;
    161       return result;
    162     }
    163   }
    164 
    165   return {
    166     RunningStatistics: RunningStatistics
    167   };
    168 });
    169 </script>
    170