shape_runtime/simd_rolling/
minmax.rs

1//! Deque-based rolling min/max operations
2
3use std::collections::VecDeque;
4
5/// Deque-based rolling minimum - O(n) amortized complexity
6///
7/// Uses a monotonic deque to achieve O(1) amortized per-element cost.
8/// This is 10-100x faster than the naive O(n*w) approach for large windows.
9///
10/// # Performance
11/// - Expected speedup: 10-100x over O(n*w) scalar (depends on window size)
12/// - Complexity: O(n) amortized
13pub fn rolling_min_deque(data: &[f64], window: usize) -> Vec<f64> {
14    let n = data.len();
15
16    if window == 0 || window > n {
17        return vec![f64::NAN; n];
18    }
19
20    let mut result = vec![f64::NAN; n];
21    // Deque stores (index, value) pairs in ascending order of values
22    let mut deque: VecDeque<(usize, f64)> = VecDeque::with_capacity(window);
23
24    for i in 0..n {
25        // Remove elements outside the window
26        while let Some(&(idx, _)) = deque.front() {
27            if idx <= i.saturating_sub(window) {
28                deque.pop_front();
29            } else {
30                break;
31            }
32        }
33
34        // Remove elements >= current value (maintain ascending order)
35        while let Some(&(_, val)) = deque.back() {
36            if val >= data[i] {
37                deque.pop_back();
38            } else {
39                break;
40            }
41        }
42
43        deque.push_back((i, data[i]));
44
45        if i >= window - 1 {
46            result[i] = deque.front().unwrap().1;
47        }
48    }
49
50    result
51}
52
53/// Deque-based rolling maximum - O(n) amortized complexity
54///
55/// # Performance
56/// - Expected speedup: 10-100x over O(n*w) scalar
57/// - Complexity: O(n) amortized
58pub fn rolling_max_deque(data: &[f64], window: usize) -> Vec<f64> {
59    let n = data.len();
60
61    if window == 0 || window > n {
62        return vec![f64::NAN; n];
63    }
64
65    let mut result = vec![f64::NAN; n];
66    // Deque stores (index, value) pairs in descending order of values
67    let mut deque: VecDeque<(usize, f64)> = VecDeque::with_capacity(window);
68
69    for i in 0..n {
70        // Remove elements outside the window
71        while let Some(&(idx, _)) = deque.front() {
72            if idx <= i.saturating_sub(window) {
73                deque.pop_front();
74            } else {
75                break;
76            }
77        }
78
79        // Remove elements <= current value (maintain descending order)
80        while let Some(&(_, val)) = deque.back() {
81            if val <= data[i] {
82                deque.pop_back();
83            } else {
84                break;
85            }
86        }
87
88        deque.push_back((i, data[i]));
89
90        if i >= window - 1 {
91            result[i] = deque.front().unwrap().1;
92        }
93    }
94
95    result
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn test_rolling_min_max_deque() {
104        let data = vec![5.0, 3.0, 7.0, 2.0, 9.0, 1.0, 8.0];
105
106        let mins = rolling_min_deque(&data, 3);
107        let maxs = rolling_max_deque(&data, 3);
108
109        assert_eq!(mins[2], 3.0); // min(5,3,7) = 3
110        assert_eq!(mins[3], 2.0); // min(3,7,2) = 2
111        assert_eq!(mins[4], 2.0); // min(7,2,9) = 2
112        assert_eq!(mins[5], 1.0); // min(2,9,1) = 1
113
114        assert_eq!(maxs[2], 7.0); // max(5,3,7) = 7
115        assert_eq!(maxs[3], 7.0); // max(3,7,2) = 7
116        assert_eq!(maxs[4], 9.0); // max(7,2,9) = 9
117        assert_eq!(maxs[5], 9.0); // max(2,9,1) = 9
118    }
119}
shape_runtime/simd_rolling/minmax.rs

shape_runtime/simd_rolling/
minmax.rs
