tycho_util/num/
rolling_percentile.rs

1use std::collections::VecDeque;
2
3use tycho_util::FastHashMap;
4
5#[derive(Debug, Clone, Default)]
6pub struct RollingPercentiles<T> {
7    window: usize,
8    buf: VecDeque<T>,
9    vals: FastHashMap<u8, T>,
10}
11
12impl<T: Copy + Ord> RollingPercentiles<T> {
13    pub fn new(window: usize) -> Self {
14        // keep at least 100 samples so P1..P99 clipping has enough history to be meaningful
15        let window = window.max(100);
16        Self {
17            window,
18            buf: VecDeque::with_capacity(window),
19            vals: Default::default(),
20        }
21    }
22
23    pub fn window(&self) -> usize {
24        self.window
25    }
26
27    pub fn push(&mut self, v: T) {
28        if self.buf.len() == self.window {
29            self.buf.pop_front();
30        }
31        self.buf.push_back(v);
32        self.vals.clear();
33    }
34
35    pub fn len(&self) -> usize {
36        self.buf.len()
37    }
38
39    pub fn is_empty(&self) -> bool {
40        self.buf.is_empty()
41    }
42
43    pub fn window_is_filled(&self) -> bool {
44        self.buf.len() >= self.window
45    }
46
47    pub fn percentile(&mut self, p: u8) -> Option<T> {
48        if self.buf.is_empty() {
49            return None;
50        }
51
52        if let Some(val) = self.vals.get(&p) {
53            return Some(*val);
54        }
55
56        let mut v: Vec<_> = self.buf.iter().copied().collect();
57        v.sort_unstable();
58
59        if v.len() == 1 {
60            let val = v[0];
61            self.vals.insert(p, val);
62            return Some(val);
63        }
64
65        let perc = p as f64;
66        let perc = perc.clamp(0.0, 100.0);
67        // use the rounded rank instead of interpolation so the result is always an observed sample
68        let pos = (perc / 100.0) * ((v.len() - 1) as f64);
69        let pos = (pos.round() as usize).min(v.len() - 1);
70
71        let val = v[pos];
72        self.vals.insert(p, val);
73        Some(val)
74    }
75
76    pub fn bounds(&mut self, p_low: u8, p_high: u8) -> Option<(T, T)> {
77        let lo = self.percentile(p_low)?;
78        let hi = self.percentile(p_high)?;
79        Some((lo.min(hi), lo.max(hi)))
80    }
81
82    pub fn clip(&mut self, x: T, p_low: u8, p_high: u8) -> Option<T> {
83        let (lo, hi) = self.bounds(p_low, p_high)?;
84        Some(x.max(lo).min(hi))
85    }
86
87    pub fn push_and_clip(&mut self, x: T, p_low: u8, p_high: u8) -> T {
88        if !self.window_is_filled() {
89            // keep raw values until the window is full enough to define stable bounds
90            self.push(x);
91            return x;
92        }
93        let clipped = self
94            .clip(x, p_low, p_high)
95            .expect("percentiles buf should contain at least one value here");
96        // push the raw sample after clipping so the current point never clips itself
97        self.push(x);
98        clipped
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::RollingPercentiles;
105
106    #[test]
107    fn push_and_clip_returns_input_before_window_is_filled() {
108        let mut pct = RollingPercentiles::new(100);
109        for _ in 0..99 {
110            assert_eq!(pct.push_and_clip(10u128, 1, 99), 10);
111        }
112        assert_eq!(pct.len(), 99);
113        assert_eq!(pct.push_and_clip(100u128, 1, 99), 100);
114        assert_eq!(pct.len(), 100);
115    }
116
117    #[test]
118    fn push_and_clip_clips_against_history_only_when_window_is_filled() {
119        let mut pct = RollingPercentiles::new(100);
120        for _ in 0..99 {
121            assert_eq!(pct.push_and_clip(10u128, 1, 99), 10);
122        }
123        assert_eq!(pct.push_and_clip(100u128, 1, 99), 100);
124        assert_eq!(pct.percentile(99), Some(10));
125        assert_eq!(pct.push_and_clip(1000u128, 1, 99), 10);
126        assert_eq!(pct.len(), 100);
127        assert_eq!(pct.percentile(100), Some(1000));
128    }
129}
tycho_util/num/rolling_percentile.rs

tycho_util/num/
rolling_percentile.rs
