blob: 38e8624f39545f79bb9350ef39d819cdab4d146d [file] [log] [blame]
<!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>