neilconway commented on code in PR #23827:
URL: https://github.com/apache/datafusion/pull/23827#discussion_r3652587412
##########
datafusion/functions-aggregate/src/min_max.rs:
##########
@@ -934,81 +888,83 @@ impl<T: Clone + PartialOrd> MovingMax<T> {
/// Creates a new `MovingMax` to keep track of the maximum in a sliding
window with
/// `capacity` allocated slots.
+ #[cfg(test)]
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Self {
- push_stack: Vec::with_capacity(capacity),
- pop_stack: Vec::with_capacity(capacity),
+ deque: VecDeque::with_capacity(capacity),
+ push_seq: 0,
+ pop_seq: 0,
}
}
/// Returns the maximum of the sliding window or `None` if the window is
empty.
#[inline]
pub fn max(&self) -> Option<&T> {
- match (self.push_stack.last(), self.pop_stack.last()) {
- (None, None) => None,
- (Some((_, max)), None) => Some(max),
- (None, Some((_, max))) => Some(max),
- (Some((_, a)), Some((_, b))) => Some(if a > b { a } else { b }),
- }
+ self.deque.front().map(|(_, val)| val)
+ }
+
+ #[inline]
+ fn check_invariants(&self) {
+ debug_assert!(self.pop_seq <= self.push_seq);
+ debug_assert!(
+ self.deque
+ .front()
+ .is_none_or(|&(front_seq, _)| front_seq >= self.pop_seq)
+ );
}
/// Pushes a new element into the sliding window.
#[inline]
pub fn push(&mut self, val: T) {
- self.push_stack.push(match self.push_stack.last() {
- Some((_, max)) => {
- if val < *max {
- (val, max.clone())
- } else {
- (val.clone(), val)
- }
- }
- None => (val.clone(), val),
- });
+ let seq = self.push_seq;
+ self.push_seq += 1;
+ while self.deque.back().is_some_and(|back_val| back_val.1 <= val) {
+ self.deque.pop_back();
+ }
+ self.deque.push_back((seq, val));
+
+ self.check_invariants();
}
- /// Removes and returns the last value of the sliding window.
+ /// Removes the oldest value from the sliding window.
+ ///
+ /// If the window is empty, this is a no-op.
#[inline]
- pub fn pop(&mut self) -> Option<T> {
- if self.pop_stack.is_empty() {
- match self.push_stack.pop() {
- Some((val, _)) => {
- let mut last = (val.clone(), val);
- self.pop_stack.push(last.clone());
- while let Some((val, _)) = self.push_stack.pop() {
- let max = if last.1 > val {
- last.1.clone()
- } else {
- val.clone()
- };
- last = (val.clone(), max);
- self.pop_stack.push(last.clone());
- }
- }
- None => return None,
- }
+ pub fn pop(&mut self) {
+ if self.is_empty() {
+ return;
+ }
+ let seq = self.pop_seq;
+ self.pop_seq += 1;
+ if self
+ .deque
+ .front()
+ .is_some_and(|front_val| front_val.0 == seq)
+ {
+ self.deque.pop_front();
}
- self.pop_stack.pop().map(|(val, _)| val)
+
+ self.check_invariants();
}
/// Returns the number of elements stored in the sliding window.
- #[inline]
+ #[cfg(test)]
pub fn len(&self) -> usize {
- self.push_stack.len() + self.pop_stack.len()
+ (self.push_seq - self.pop_seq) as usize
}
/// Returns `true` if the moving window contains no elements.
#[inline]
pub fn is_empty(&self) -> bool {
- self.len() == 0
+ self.push_seq == self.pop_seq
}
/// Heap bytes owned by the two stack buffers plus each stored `T`'s
Review Comment:
Update this comment.
##########
datafusion/functions-aggregate/src/min_max.rs:
##########
@@ -731,201 +732,154 @@ impl Accumulator for SlidingMinAccumulator {
/// Keep track of the minimum value in a sliding window.
///
-/// The implementation is taken from
<https://github.com/spebern/moving_min_max/blob/master/src/lib.rs>
+/// `MovingMin` keeps track of the minimum value in a sliding window using a
+/// monotonic deque. Each element is stored with its sequence number, and the
+/// deque maintains candidate elements in strictly increasing value order.
Review Comment:
"Strictly increasing" is a bit misleading, since we only require
`PartialOrd`. "in ascending order" instead?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
