1use std::f64::consts::PI;
9
10const EXACT_CAP: usize = 50_000;
13
14const COMPRESSION: f64 = 200.0;
16
17const BUFFER: usize = 1024;
19
20#[derive(Clone)]
22pub struct Digest {
23 exact: Vec<f64>,
24 sketch: Option<TDigest>,
25 count: u64,
26 min: f64,
27 max: f64,
28 sum: f64,
29}
30
31impl Default for Digest {
32 fn default() -> Self { Self::new() }
33}
34
35impl Digest {
36 pub fn new() -> Self {
37 Self {
38 exact: Vec::new(),
39 sketch: None,
40 count: 0,
41 min: f64::INFINITY,
42 max: f64::NEG_INFINITY,
43 sum: 0.0,
44 }
45 }
46
47 pub fn add(&mut self, x: f64) {
50 if !x.is_finite() {
51 return;
52 }
53 self.count += 1;
54 self.sum += x;
55 self.min = self.min.min(x);
56 self.max = self.max.max(x);
57
58 if let Some(s) = &mut self.sketch {
59 s.add(x);
60 return;
61 }
62 self.exact.push(x);
63 if self.exact.len() > EXACT_CAP {
64 let mut s = TDigest::new(COMPRESSION);
65 s.add_slice(&self.exact);
66 self.exact = Vec::new();
67 self.sketch = Some(s);
68 }
69 }
70
71 pub fn count(&self) -> u64 { self.count }
72
73 pub fn min(&self) -> f64 { self.min }
74
75 pub fn max(&self) -> f64 { self.max }
76
77 pub fn mean(&self) -> f64 {
78 if self.count == 0 {
79 f64::NAN
80 } else {
81 self.sum / self.count as f64
82 }
83 }
84
85 pub fn is_exact(&self) -> bool { self.sketch.is_none() }
87
88 pub fn quantile(&mut self, q: f64) -> f64 {
90 if self.count == 0 {
91 return f64::NAN;
92 }
93 match &mut self.sketch {
94 Some(s) => s.quantile(q).clamp(self.min, self.max),
95 None => {
96 self.exact.sort_by(|a, b| a.partial_cmp(b).expect("finite"));
97 let i = (((self.exact.len() - 1) as f64) * q).round() as usize;
98 self.exact[i]
99 }
100 }
101 }
102}
103
104#[derive(Clone, Copy)]
105struct Centroid {
106 mean: f64,
107 weight: f64,
108}
109
110#[derive(Clone)]
113struct TDigest {
114 centroids: Vec<Centroid>,
115 buffer: Vec<f64>,
116 delta: f64,
117}
118
119impl TDigest {
120 fn new(delta: f64) -> Self {
121 Self {
122 centroids: Vec::new(),
123 buffer: Vec::new(),
124 delta,
125 }
126 }
127
128 fn add(&mut self, x: f64) {
129 self.buffer.push(x);
130 if self.buffer.len() >= BUFFER {
131 self.flush();
132 }
133 }
134
135 fn add_slice(&mut self, xs: &[f64]) {
136 for &x in xs {
137 self.add(x);
138 }
139 }
140
141 fn flush(&mut self) {
143 if self.buffer.is_empty() {
144 return;
145 }
146 let mut pts: Vec<Centroid> =
147 Vec::with_capacity(self.centroids.len() + self.buffer.len());
148 pts.append(&mut self.centroids);
149 for &x in &self.buffer {
150 pts.push(Centroid { mean: x, weight: 1.0 });
151 }
152 self.buffer.clear();
153 pts.sort_by(|a, b| a.mean.partial_cmp(&b.mean).expect("finite"));
154
155 let total: f64 = pts.iter().map(|c| c.weight).sum();
156 let mut merged: Vec<Centroid> = Vec::new();
157 let mut cur = pts[0];
158 let mut w_before = 0.0;
159 for p in &pts[1..] {
160 let q0 = w_before / total;
161 let q1 = (w_before + cur.weight + p.weight) / total;
162 if k(q1, self.delta) - k(q0, self.delta) <= 1.0 {
163 let w = cur.weight + p.weight;
164 cur.mean += (p.mean - cur.mean) * p.weight / w;
165 cur.weight = w;
166 } else {
167 merged.push(cur);
168 w_before += cur.weight;
169 cur = *p;
170 }
171 }
172 merged.push(cur);
173 self.centroids = merged;
174 }
175
176 fn quantile(&mut self, q: f64) -> f64 {
177 self.flush();
178 let cs = &self.centroids;
179 match cs.len() {
180 0 => return f64::NAN,
181 1 => return cs[0].mean,
182 _ => {}
183 }
184 let total: f64 = cs.iter().map(|c| c.weight).sum();
185 let target = q * total;
186
187 let mut centers = Vec::with_capacity(cs.len());
189 let mut cum = 0.0;
190 for c in cs {
191 centers.push(cum + c.weight / 2.0);
192 cum += c.weight;
193 }
194 if target <= centers[0] {
195 return cs[0].mean;
196 }
197 if target >= centers[cs.len() - 1] {
198 return cs[cs.len() - 1].mean;
199 }
200 for i in 1..cs.len() {
201 if target <= centers[i] {
202 let t =
203 (target - centers[i - 1]) / (centers[i] - centers[i - 1]);
204 return cs[i - 1].mean + (cs[i].mean - cs[i - 1].mean) * t;
205 }
206 }
207 cs[cs.len() - 1].mean
208 }
209}
210
211fn k(q: f64, delta: f64) -> f64 {
215 let q = q.clamp(0.0, 1.0);
216 delta / (2.0 * PI) * (2.0 * q - 1.0).asin()
217}
218
219#[cfg(test)]
220mod tests {
221 use super::*;
222
223 #[test]
224 fn exact_under_the_cap() {
225 let mut d = Digest::new();
226 for i in 1..=100 {
227 d.add(i as f64);
228 }
229 assert!(d.is_exact());
230 assert_eq!(d.count(), 100);
231 assert_eq!(d.min(), 1.0);
232 assert_eq!(d.max(), 100.0);
233 assert!((d.mean() - 50.5).abs() < 1e-9);
234 assert_eq!(d.quantile(0.5), 51.0);
236 assert_eq!(d.quantile(0.0), 1.0);
237 assert_eq!(d.quantile(1.0), 100.0);
238 }
239
240 #[test]
241 fn non_finite_is_ignored() {
242 let mut d = Digest::new();
243 d.add(1.0);
244 d.add(f64::NAN);
245 d.add(f64::INFINITY);
246 d.add(3.0);
247 assert_eq!(d.count(), 2);
248 assert_eq!(d.max(), 3.0);
249 }
250
251 #[test]
252 fn approximates_past_the_cap_with_small_error() {
253 let mut d = Digest::new();
256 let n = 1_000_000.0;
257 for i in 1..=1_000_000u64 {
258 d.add(i as f64);
259 }
260 assert!(!d.is_exact());
261 assert_eq!(d.count(), 1_000_000);
262 assert_eq!(d.min(), 1.0);
263 assert_eq!(d.max(), 1_000_000.0);
264 assert!((d.mean() - 500_000.5).abs() < 1.0);
265
266 let check = |q: f64, d: &mut Digest| {
267 let got = d.quantile(q);
268 let want = q * n;
269 let err = (got - want).abs() / n;
270 assert!(err < 0.01, "q{q}: got {got}, want ~{want}, err {err}");
271 };
272 check(0.5, &mut d);
273 check(0.9, &mut d);
274 check(0.99, &mut d);
275 check(0.999, &mut d);
276 }
277
278 #[test]
279 fn skewed_distribution_tail_accuracy() {
280 let mut d = Digest::new();
282 for i in 0..200_000 {
283 d.add((i % 100) as f64); }
285 for _ in 0..2_000 {
286 d.add(10_000.0); }
288 assert!(!d.is_exact());
289 assert!(d.quantile(0.5) < 100.0);
290 assert_eq!(d.max(), 10_000.0);
291 }
292}