| <!DOCTYPE html> |
| <!-- |
| Copyright (c) 2014 The Chromium Authors. All rights reserved. |
| Use of this source code is governed by a BSD-style license that can be |
| found in the LICENSE file. |
| --> |
| <link rel="import" href="/tracing/base/range.html"> |
| <script> |
| 'use strict'; |
| |
| tr.exportTo('tr.b', function() { |
| |
| function identity(d) { |
| return d; |
| } |
| |
| function Statistics() { |
| } |
| |
| /* Returns the quotient, or zero if the denominator is zero.*/ |
| Statistics.divideIfPossibleOrZero = function(numerator, denominator) { |
| if (denominator === 0) |
| return 0; |
| return numerator / denominator; |
| }; |
| |
| Statistics.sum = function(ary, opt_func, opt_this) { |
| var func = opt_func || identity; |
| var ret = 0; |
| for (var i = 0; i < ary.length; i++) |
| ret += func.call(opt_this, ary[i], i); |
| return ret; |
| }; |
| |
| Statistics.mean = function(ary, opt_func, opt_this) { |
| return Statistics.sum(ary, opt_func, opt_this) / ary.length; |
| }; |
| |
| // Returns undefined if the sum of the weights is zero. |
| Statistics.weightedMean = function( |
| ary, weightCallback, opt_valueCallback, opt_this) { |
| var valueCallback = opt_valueCallback || identity; |
| var numerator = 0; |
| var denominator = 0; |
| |
| for (var i = 0; i < ary.length; i++) { |
| var value = valueCallback.call(opt_this, ary[i], i); |
| if (value === undefined) |
| continue; |
| var weight = weightCallback.call(opt_this, ary[i], i, value); |
| numerator += weight * value; |
| denominator += weight; |
| } |
| |
| if (denominator === 0) |
| return undefined; |
| |
| return numerator / denominator; |
| }; |
| |
| Statistics.variance = function(ary, opt_func, opt_this) { |
| var func = opt_func || identity; |
| var mean = Statistics.mean(ary, func, opt_this); |
| var sumOfSquaredDistances = Statistics.sum( |
| ary, |
| function(d, i) { |
| var v = func.call(this, d, i) - mean; |
| return v * v; |
| }, |
| opt_this); |
| return sumOfSquaredDistances / (ary.length - 1); |
| }; |
| |
| Statistics.stddev = function(ary, opt_func, opt_this) { |
| return Math.sqrt( |
| Statistics.variance(ary, opt_func, opt_this)); |
| }; |
| |
| Statistics.max = function(ary, opt_func, opt_this) { |
| var func = opt_func || identity; |
| var ret = -Infinity; |
| for (var i = 0; i < ary.length; i++) |
| ret = Math.max(ret, func.call(opt_this, ary[i], i)); |
| return ret; |
| }; |
| |
| Statistics.min = function(ary, opt_func, opt_this) { |
| var func = opt_func || identity; |
| var ret = Infinity; |
| for (var i = 0; i < ary.length; i++) |
| ret = Math.min(ret, func.call(opt_this, ary[i], i)); |
| return ret; |
| }; |
| |
| Statistics.range = function(ary, opt_func, opt_this) { |
| var func = opt_func || identity; |
| var ret = new tr.b.Range(); |
| for (var i = 0; i < ary.length; i++) |
| ret.addValue(func.call(opt_this, ary[i], i)); |
| return ret; |
| }; |
| |
| Statistics.percentile = function(ary, percent, opt_func, opt_this) { |
| if (!(percent >= 0 && percent <= 1)) |
| throw new Error('percent must be [0,1]'); |
| |
| var func = opt_func || identity; |
| var tmp = new Array(ary.length); |
| for (var i = 0; i < ary.length; i++) |
| tmp[i] = func.call(opt_this, ary[i], i); |
| tmp.sort(); |
| var idx = Math.floor((ary.length - 1) * percent); |
| return tmp[idx]; |
| }; |
| |
| /* Clamp a value between some low and high value. */ |
| Statistics.clamp = function(value, opt_low, opt_high) { |
| opt_low = opt_low || 0.0; |
| opt_high = opt_high || 1.0; |
| return Math.min(Math.max(value, opt_low), opt_high); |
| }; |
| |
| /** |
| * Sorts the samples, and map them linearly to the range [0,1]. |
| * |
| * They're mapped such that for the N samples, the first sample is 0.5/N and |
| * the last sample is (N-0.5)/N. |
| * |
| * Background: The discrepancy of the sample set i/(N-1); i=0, ..., N-1 is |
| * 2/N, twice the discrepancy of the sample set (i+1/2)/N; i=0, ..., N-1. In |
| * our case we don't want to distinguish between these two cases, as our |
| * original domain is not bounded (it is for Monte Carlo integration, where |
| * discrepancy was first used). |
| **/ |
| Statistics.normalizeSamples = function(samples) { |
| if (samples.length === 0) { |
| return { |
| normalized_samples: samples, |
| scale: 1.0 |
| }; |
| } |
| // Create a copy to make sure that we don't mutate original |samples| input. |
| samples = samples.slice().sort( |
| function(a, b) { |
| return a - b; |
| } |
| ); |
| var low = Math.min.apply(null, samples); |
| var high = Math.max.apply(null, samples); |
| var new_low = 0.5 / samples.length; |
| var new_high = (samples.length - 0.5) / samples.length; |
| if (high - low === 0.0) { |
| // Samples is an array of 0.5 in this case. |
| samples = Array.apply(null, new Array(samples.length)).map( |
| function() { return 0.5;}); |
| return { |
| normalized_samples: samples, |
| scale: 1.0 |
| }; |
| } |
| var scale = (new_high - new_low) / (high - low); |
| for (var i = 0; i < samples.length; i++) { |
| samples[i] = (samples[i] - low) * scale + new_low; |
| } |
| return { |
| normalized_samples: samples, |
| scale: scale |
| }; |
| }; |
| |
| /** |
| * Computes the discrepancy of a set of 1D samples from the interval [0,1]. |
| * |
| * The samples must be sorted. We define the discrepancy of an empty set |
| * of samples to be zero. |
| * |
| * http://en.wikipedia.org/wiki/Low-discrepancy_sequence |
| * http://mathworld.wolfram.com/Discrepancy.html |
| */ |
| Statistics.discrepancy = function(samples, opt_location_count) { |
| if (samples.length === 0) |
| return 0.0; |
| |
| var max_local_discrepancy = 0; |
| var inv_sample_count = 1.0 / samples.length; |
| var locations = []; |
| // For each location, stores the number of samples less than that location. |
| var count_less = []; |
| // For each location, stores the number of samples less than or equal to |
| // that location. |
| var count_less_equal = []; |
| |
| if (opt_location_count !== undefined) { |
| // Generate list of equally spaced locations. |
| var sample_index = 0; |
| for (var i = 0; i < opt_location_count; i++) { |
| var location = i / (opt_location_count - 1); |
| locations.push(location); |
| while (sample_index < samples.length && |
| samples[sample_index] < location) { |
| sample_index += 1; |
| } |
| count_less.push(sample_index); |
| while (sample_index < samples.length && |
| samples[sample_index] <= location) { |
| sample_index += 1; |
| } |
| count_less_equal.push(sample_index); |
| } |
| } else { |
| // Populate locations with sample positions. Append 0 and 1 if necessary. |
| if (samples[0] > 0.0) { |
| locations.push(0.0); |
| count_less.push(0); |
| count_less_equal.push(0); |
| } |
| for (var i = 0; i < samples.length; i++) { |
| locations.push(samples[i]); |
| count_less.push(i); |
| count_less_equal.push(i + 1); |
| } |
| if (samples[-1] < 1.0) { |
| locations.push(1.0); |
| count_less.push(samples.length); |
| count_less_equal.push(samples.length); |
| } |
| } |
| // Iterate over the intervals defined by any pair of locations. |
| for (var i = 0; i < locations.length; i++) { |
| for (var j = i + 1; j < locations.length; j++) { |
| // Length of interval |
| var length = locations[j] - locations[i]; |
| |
| // Local discrepancy for closed interval |
| var count_closed = count_less_equal[j] - count_less[i]; |
| var local_discrepancy_closed = Math.abs( |
| count_closed * inv_sample_count - length); |
| var max_local_discrepancy = Math.max( |
| local_discrepancy_closed, max_local_discrepancy); |
| |
| // Local discrepancy for open interval |
| var count_open = count_less[j] - count_less_equal[i]; |
| var local_discrepancy_open = Math.abs( |
| count_open * inv_sample_count - length); |
| var max_local_discrepancy = Math.max( |
| local_discrepancy_open, max_local_discrepancy); |
| } |
| } |
| return max_local_discrepancy; |
| }; |
| |
| /** |
| * A discrepancy based metric for measuring timestamp jank. |
| * |
| * timestampsDiscrepancy quantifies the largest area of jank observed in a |
| * series of timestamps. Note that this is different from metrics based on |
| * the max_time_interval. For example, the time stamp series A = [0,1,2,3,5,6] |
| * and B = [0,1,2,3,5,7] have the same max_time_interval = 2, but |
| * Discrepancy(B) > Discrepancy(A). |
| * |
| * Two variants of discrepancy can be computed: |
| * |
| * Relative discrepancy is following the original definition of |
| * discrepancy. It characterized the largest area of jank, relative to the |
| * duration of the entire time stamp series. We normalize the raw results, |
| * because the best case discrepancy for a set of N samples is 1/N (for |
| * equally spaced samples), and we want our metric to report 0.0 in that |
| * case. |
| * |
| * Absolute discrepancy also characterizes the largest area of jank, but its |
| * value wouldn't change (except for imprecisions due to a low |
| * |interval_multiplier|) if additional 'good' intervals were added to an |
| * exisiting list of time stamps. Its range is [0,inf] and the unit is |
| * milliseconds. |
| * |
| * The time stamp series C = [0,2,3,4] and D = [0,2,3,4,5] have the same |
| * absolute discrepancy, but D has lower relative discrepancy than C. |
| * |
| * |timestamps| may be a list of lists S = [S_1, S_2, ..., S_N], where each |
| * S_i is a time stamp series. In that case, the discrepancy D(S) is: |
| * D(S) = max(D(S_1), D(S_2), ..., D(S_N)) |
| **/ |
| Statistics.timestampsDiscrepancy = function(timestamps, opt_absolute, |
| opt_location_count) { |
| if (timestamps.length === 0) |
| return 0.0; |
| |
| if (opt_absolute === undefined) |
| opt_absolute = true; |
| |
| if (Array.isArray(timestamps[0])) { |
| var range_discrepancies = timestamps.map(function(r) { |
| return Statistics.timestampsDiscrepancy(r); |
| }); |
| return Math.max.apply(null, range_discrepancies); |
| } |
| |
| var s = Statistics.normalizeSamples(timestamps); |
| var samples = s.normalized_samples; |
| var sample_scale = s.scale; |
| var discrepancy = Statistics.discrepancy(samples, opt_location_count); |
| var inv_sample_count = 1.0 / samples.length; |
| if (opt_absolute === true) { |
| // Compute absolute discrepancy |
| discrepancy /= sample_scale; |
| } else { |
| // Compute relative discrepancy |
| discrepancy = Statistics.clamp( |
| (discrepancy - inv_sample_count) / (1.0 - inv_sample_count)); |
| } |
| return discrepancy; |
| }; |
| |
| /** |
| * A discrepancy based metric for measuring duration jank. |
| * |
| * DurationsDiscrepancy computes a jank metric which measures how irregular a |
| * given sequence of intervals is. In order to minimize jank, each duration |
| * should be equally long. This is similar to how timestamp jank works, |
| * and we therefore reuse the timestamp discrepancy function above to compute |
| * a similar duration discrepancy number. |
| * |
| * Because timestamp discrepancy is defined in terms of timestamps, we first |
| * convert the list of durations to monotonically increasing timestamps. |
| * |
| * Args: |
| * durations: List of interval lengths in milliseconds. |
| * absolute: See TimestampsDiscrepancy. |
| * opt_location_count: See TimestampsDiscrepancy. |
| **/ |
| Statistics.durationsDiscrepancy = function( |
| durations, opt_absolute, opt_location_count) { |
| if (durations.length === 0) |
| return 0.0; |
| |
| var timestamps = durations.reduce(function(prev, curr, index, array) { |
| prev.push(prev[prev.length - 1] + curr); |
| return prev; |
| }, [0]); |
| return Statistics.timestampsDiscrepancy( |
| timestamps, opt_absolute, opt_location_count); |
| }; |
| |
| |
| /** |
| * A mechanism to uniformly sample elements from an arbitrary long stream. |
| * |
| * Call this method every time a new element is obtained from the stream, |
| * passing always the same |samples| array and the |numSamples| you desire. |
| * Also pass in the current |streamLength|, which is the same as the index of |
| * |newElement| within that stream. |
| * |
| * The |samples| array will possibly be updated, replacing one of its element |
| * with |newElements|. The length of |samples| will not be more than |
| * |numSamples|. |
| * |
| * This method guarantees that after |streamLength| elements have been |
| * processed each one has equal probability of being in |samples|. The order |
| * of samples is not preserved though. |
| * |
| * Args: |
| * samples: Array of elements that have already been selected. Start with []. |
| * streamLength: The current length of the stream, up to |newElement|. |
| * newElement: The element that was just extracted from the stream. |
| * numSamples: The total number of samples desired. |
| **/ |
| Statistics.uniformlySampleStream = function(samples, streamLength, newElement, |
| numSamples) { |
| if (streamLength <= numSamples) { |
| if (samples.length >= streamLength) |
| samples[streamLength - 1] = newElement; |
| else |
| samples.push(newElement); |
| return; |
| } |
| |
| var probToKeep = numSamples / streamLength; |
| if (Math.random() > probToKeep) |
| return; // New sample was rejected. |
| |
| // Keeping it, replace an alement randomly. |
| var index = Math.floor(Math.random() * numSamples); |
| samples[index] = newElement; |
| }; |
| |
| /** |
| * A mechanism to merge two arrays of uniformly sampled elements in a way that |
| * ensures elements in the final array are still sampled uniformly. |
| * |
| * This works similarly to sampleStreamUniform. The |samplesA| array will be |
| * updated, some of its elements replaced by elements from |samplesB| in a |
| * way that ensure that elements will be sampled uniformly. |
| * |
| * Args: |
| * samplesA: Array of uniformly sampled elements, will be updated. |
| * streamLengthA: The length of the stream from which |samplesA| was sampled. |
| * samplesB: Other array of uniformly sampled elements, will NOT be updated. |
| * streamLengthB: The length of the stream from which |samplesB| was sampled. |
| * numSamples: The total number of samples desired, both in |samplesA| and |
| * |samplesB|. |
| **/ |
| Statistics.mergeSampledStreams = function( |
| samplesA, streamLengthA, |
| samplesB, streamLengthB, numSamples) { |
| if (streamLengthB < numSamples) { |
| // samplesB has not reached max capacity so every sample of stream B were |
| // chosen with certainty. Add them one by one into samplesA. |
| var nbElements = Math.min(streamLengthB, samplesB.length); |
| for (var i = 0; i < nbElements; ++i) { |
| Statistics.uniformlySampleStream(samplesA, streamLengthA + i + 1, |
| samplesB[i], numSamples); |
| } |
| return; |
| } |
| if (streamLengthA < numSamples) { |
| // samplesA has not reached max capacity so every sample of stream A were |
| // chosen with certainty. Add them one by one into samplesB. |
| var nbElements = Math.min(streamLengthA, samplesA.length); |
| var tempSamples = samplesB.slice(); |
| for (var i = 0; i < nbElements; ++i) { |
| Statistics.uniformlySampleStream(tempSamples, streamLengthB + i + 1, |
| samplesA[i], numSamples); |
| } |
| // Copy that back into the first vector. |
| for (var i = 0; i < tempSamples.length; ++i) { |
| samplesA[i] = tempSamples[i]; |
| } |
| return; |
| } |
| |
| // Both sample arrays are at max capacity, use the power of maths! |
| // Elements in samplesA have been selected with probability |
| // numSamples / streamLengthA. Same for samplesB. For each index of the |
| // array we keep samplesA[i] with probability |
| // P = streamLengthA / (streamLengthA + streamLengthB) |
| // and replace it with samplesB[i] with probability 1-P. |
| // The total probability of keeping it is therefore |
| // numSamples / streamLengthA * |
| // streamLengthA / (streamLengthA + streamLengthB) |
| // = numSamples / (streamLengthA + streamLengthB) |
| // A similar computation shows we have the same probability of keeping any |
| // element in samplesB. Magic! |
| var nbElements = Math.min(numSamples, samplesB.length); |
| var probOfSwapping = streamLengthB / (streamLengthA + streamLengthB); |
| for (var i = 0; i < nbElements; ++i) { |
| if (Math.random() < probOfSwapping) { |
| samplesA[i] = samplesB[i]; |
| } |
| } |
| }; |
| |
| return { |
| Statistics: Statistics |
| }; |
| }); |
| </script> |