/
histogram.ts
118 lines (99 loc) · 3.07 KB
/
histogram.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
import type { Bucketing } from "./bucketing.js";
import { saturatingAdd } from "../core/utils.js";
export enum HistogramType {
// A histogram with linear distributed buckets.
linear = "linear",
// A histogram with exponential distributed buckets.
exponential = "exponential",
}
/**
* A histogram.
*
* Stores the counts per bucket and tracks the count of added samples and the total sum.
* The bucketing algorithm can be changed.
*/
export class Histogram {
// Mapping bucket's minimum to sample count.
values: Record<number, number>;
// The count of samples added.
count: number;
// The total sum of samples.
sum: number;
// The bucketing algorithm used.
bucketing: Bucketing;
constructor(bucketing: Bucketing) {
this.values = {};
this.count = 0;
this.sum = 0;
this.bucketing = bucketing;
}
/**
* Gets the number of buckets in the Histogram.
*
* @returns The number of buckets in the histogram.
*/
bucketCount(): number {
return Object.keys(this.values).length;
}
/**
* Adds a single value to the histogram.
*
* @param sample The value to add to the histogram.
*/
accumulate(sample: number) {
const bucketMin = this.bucketing.sampleToBucketMinimum(sample);
// Fill in missing entires with 0s.
if (!this.values[bucketMin]) {
this.values[bucketMin] = 0;
}
this.values[bucketMin] = this.values[bucketMin] + 1;
this.sum = saturatingAdd(this.sum, sample);
this.count += 1;
}
/**
* Checks if this histogram recorded any values.
*
* @returns Whether the histogram has any values.
*/
isEmpty(): boolean {
return this.count === 0;
}
/**
* Gets a snapshot of all values from the first bucket until one past the last filled bucket,
* filling in empty buckets with 0.
*
* If a `snapshotOverride` function has been provided, we will provide a snapshot using that
* function rather than the default snapshot. This helps handle scenarios like Functional histograms
* where buckets aren't precomputed, so you cannot get `ranges`.
*
* @returns A snapshot of the stored values.
*/
snapshotValues(): Record<number, number> {
if (this.bucketing.snapshotOverride) {
return this.bucketing.snapshotOverride(this.values);
} else {
return this.getDefaultSnapshot();
}
}
private getDefaultSnapshot(): Record<number, number> {
const valuesClone = { ...this.values };
const maxBucket = Object.keys(valuesClone).reduce((prev, curr) => {
const prevAsNum = Number(prev);
const currAsNum = Number(curr);
return currAsNum > prevAsNum ? curr : prev;
});
const ranges = this.bucketing.ranges();
for (const minBucket of ranges) {
if (!valuesClone[minBucket]) {
valuesClone[minBucket] = 0;
}
if (minBucket > Number(maxBucket)) {
break;
}
}
return valuesClone;
}
}