Skip to main content

jlf_core/
digest.rs

1//! Bounded-memory streaming quantiles.
2//!
3//! [`Digest`] keeps values verbatim while there are few of them — so typical
4//! inputs get *exact* percentiles — and folds into a t-digest sketch once it
5//! crosses a cap, trading a small approximation for constant memory on huge
6//! streams. `count`, `min`, `max` and `mean` stay exact in either mode.
7
8use std::f64::consts::PI;
9
10/// Below this many values a digest stores them verbatim and answers percentiles
11/// exactly; past it, values fold into the sketch.
12const EXACT_CAP: usize = 50_000;
13
14/// t-digest compression: higher = more centroids, more accuracy, more memory.
15const COMPRESSION: f64 = 200.0;
16
17/// Flush buffered singletons into centroids once this many accumulate.
18const BUFFER: usize = 1024;
19
20/// A streaming numeric summary with bounded memory.
21#[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    /// Record a value. Non-finite values (NaN, ±∞) are ignored so they can't
48    /// poison min/max/sum or break the sort.
49    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    /// Whether percentiles are still exact (`true`) or sketch-approximated.
86    pub fn is_exact(&self) -> bool { self.sketch.is_none() }
87
88    /// The `q`-quantile (`0.0..=1.0`). Exact while under the cap.
89    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/// A merging t-digest: a sorted set of weighted centroids whose sizes are
111/// bounded by the `asin` scale function, so accuracy is highest at the tails.
112#[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    /// Merge buffered singletons into the centroid set in one sorted pass.
142    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        // Cumulative weight at the center of each centroid.
188        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
211/// The t-digest scale function `k1`: a centroid spanning cumulative quantiles
212/// `[q0, q1]` is allowed while `k(q1) - k(q0) <= 1`, which keeps centroids
213/// small near 0 and 1 (accurate tails) and larger in the middle.
214fn 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        // round((n-1)*q): p50 -> index 50 -> value 51
235        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        // A uniform 1..=1_000_000 crosses the cap, so percentiles come from the
254        // sketch. They should track the true quantiles within ~1%.
255        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        // Most values small, a heavy tail; p99 should land in the tail region.
281        let mut d = Digest::new();
282        for i in 0..200_000 {
283            d.add((i % 100) as f64); // 0..99 bulk
284        }
285        for _ in 0..2_000 {
286            d.add(10_000.0); // 1% tail
287        }
288        assert!(!d.is_exact());
289        assert!(d.quantile(0.5) < 100.0);
290        assert_eq!(d.max(), 10_000.0);
291    }
292}