tracing/tracing/base/piecewise_linear_function.html - Issue 2771723003: [tracing] Move math utilities from base into their own subdirectory (attempt 2)

Side by Side Diff: tracing/tracing/base/piecewise_linear_function.html

Issue 2771723003: [tracing] Move math utilities from base into their own subdirectory (attempt 2) (Closed)

Patch Set: rebase Created 3 years, 9 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
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 var PERCENTILE_PRECISION = 1e-7;

15 /**

16 * A function that consists of linear pieces.

17 * See https://en.wikipedia.org/wiki/Piecewise_linear_function.

18 * @constructor

19 */

20 function PiecewiseLinearFunction() {

21 this.pieces = [];

22 }

23

24 PiecewiseLinearFunction.prototype = {

25 /**

26 * Push a linear piece defined by linear interpolation between.

27 * (x1, y1) and (x2, y2).

28 * Pieces must be pushed in the order of increasing x coordinate.

29 */

30 push: function(x1, y1, x2, y2) {

31 if (x1 >= x2)

32 throw new Error('Invalid segment');

33 if (this.pieces.length > 0 &&

34 this.pieces[this.pieces.length - 1].x2 > x1) {

35 throw new Error('Potentially overlapping segments');

36 }

37 if (x1 < x2)

38 this.pieces.push(new Piece(x1, y1, x2, y2));

39 },

40

41 /**

42 * Returns the size of the set A such that for all x in A: f(x) < y.

43 */

44 partBelow: function(y) {

45 return this.pieces.reduce((acc, p) => (acc + p.partBelow(y)), 0);

46 },

47

48 get min() {

49 return this.pieces.reduce((acc, p) => Math.min(acc, p.min), Infinity);

50 },

51

52 get max() {

53 return this.pieces.reduce((acc, p) => Math.max(acc, p.max), -Infinity);

54 },

55

56 get average() {

57 var weightedSum = 0;

58 var totalWeight = 0;

59 this.pieces.forEach(function(piece) {

60 weightedSum += piece.width * piece.average;

61 totalWeight += piece.width;

62 });

63 if (totalWeight === 0)

64 return 0;

65 return weightedSum / totalWeight;

66 },

67

68 /**

69 * Returns the minimum possible value y such that the percentage of x points

70 * that have f(x) <= y is approximately equal to the given \|percent\|.

71 */

72 percentile: function(percent) {

73 if (!(percent >= 0 && percent <= 1))

74 throw new Error('percent must be [0,1]');

75 var lower = this.min;

76 var upper = this.max;

77 var total = this.partBelow(upper);

78 if (total === 0)

79 return 0;

80 while (upper - lower > PERCENTILE_PRECISION) {

81 var middle = (lower + upper) / 2;

82 var below = this.partBelow(middle);

83 if (below / total < percent)

84 lower = middle;

85 else

86 upper = middle;

87 }

88 return (lower + upper) / 2;

89 }

90 };

91

92 /**

93 * A linear segment from (x1, y1) to (x2, y2).

94 * @constructor

95 */

96 function Piece(x1, y1, x2, y2) {

97 this.x1 = x1;

98 this.y1 = y1;

99 this.x2 = x2;

100 this.y2 = y2;

101 }

102

103 Piece.prototype = {

104 /**

105 * The total length of all x points such that f(x) < y.

106 * More formally:

107 * max(x2 - x1) such that for all x in [x1 .. x2]: f(x) < y.

108 */

109 partBelow: function(y) {

110 var width = this.width;

111 if (width === 0)

112 return 0;

113 var minY = this.min;

114 var maxY = this.max;

115 if (y >= maxY)

116 return width;

117 if (y < minY)

118 return 0;

119 return (y - minY) / (maxY - minY) * width;

120 },

121

122 get min() {

123 return Math.min(this.y1, this.y2);

124 },

125

126 get max() {

127 return Math.max(this.y1, this.y2);

128 },

129

130 get average() {

131 return (this.y1 + this.y2) / 2;

132 },

133

134 get width() {

135 return this.x2 - this.x1;

136 }

137 };

138

139 return {

140 PiecewiseLinearFunction,

141 };

142 });

143 </script>

OLD	NEW

« no previous file with comments | « tracing/tracing/base/math_test.html ('k') | tracing/tracing/base/piecewise_linear_function_test.html » ('j') | no next file with comments »