Sliding window max/min algorithm without dynamic allocations

Question

I'm working on a suite of DSP tools in Rust, and one of the features of the library is a collection of windowed statistics (mean, RMS, min, max, median, etc) on streams of floating-point samples. For instance, if the window size is 7, then the windowed min is the smallest of the last 7 items in the stream (the window), and the windowed mean is the average of the last 7 items in the stream. The user provides an iterator of floats and a fixed-size mutable slice/array of floats as inputs and gets back an iterator that lazily calculates the desired stat one sample at a time. The contents of the float slice/array become the initial window and can be used as scratch space internally. This slice/array also determines the sliding window size.

// A sliding mean with a window size of 64, initially filled with 0.42.
let sample_iter = /* an iterator that yields floats */;
let buffer = [0.42; 64];
let sliding_mean_iter = SlidingMean::new(sample_iter, buffer);

I'd ideally like to have my library also usable in an embedded environment, and so far I've been able to do so by not using any dynamic memory allocations.

As of now, I have efficient mean and RMS implementations, but I'm stumped on the windowed min/max. Looking up sliding window min/max algorithms online[1][2], I see that:

1. A naive approach of scanning the window after each update leads to an O(nk) runtime, where n is the length of the input iterator and k is the window length. This feels like it could be inefficient for larger window sizes.
2. Using a deque allows for an efficient implementation of O(n) (with amortized insertion of O(1)), but using a deque would require dynamic allocations.
3. Since the passed-in buffer is overloaded to both set the initial window contents as well as to serve as scratch space, I can't mess with the type of that, it has to stay as a slice/array of plain floats. This means I can't make it an array of (int, float) to store array indices alongside the data, for example.

Are there any clever tricks or optimizations I can use to have my cake (efficient sliding min/max) and eat it too (avoid having memory allocations)?

Here's a walkthrough example of a sliding max with window length 3:

Initial samples: {3 4 3 1 5 2 7 3 4 1}

Step 1: {[3 4 3] 1 5 2 7 3 4 1} -> The max of [3 4 3] is 4.
Step 2: {3 [4 3 1] 5 2 7 3 4 1} -> The max of [4 3 1] is 4.
Step 3: {3 4 [3 1 5] 2 7 3 4 1} -> The max of [3 1 5] is 5.
Step 4: {3 4 3 [1 5 2] 7 3 4 1} -> The max of [1 5 2] is 5.
Step 5: {3 4 3 1 [5 2 7] 3 4 1} -> The max of [5 2 7] is 7.
Step 6: {3 4 3 1 5 [2 7 3] 4 1} -> The max of [2 7 3] is 7.
Step 7: {3 4 3 1 5 2 [7 3 4] 1} -> The max of [7 3 4] is 7.
Step 8: {3 4 3 1 5 2 7 [3 4 1]} -> The max of [3 4 1] is 4.
Done.

The output is therefore {4 4 5 5 7 7 7 4}.

Answer 1

Change your API so that the user must provide a buffer of type (f32, isize) (or a wrapper type thereof) so that you can store the indices associated with each sample in your window.

Then you can turn this buffer into a double-ended queue by having two indices, head and tail, and forming a ring buffer.

Then you can apply the algorithm I described here to get a constant amortized time algorithm.

Answer 2

Change the API. All reasonable data structures require more space. There is no solution that I am aware of within your constraints. Your current API imposes a limitation on the set of data structures you can use that is too strict to admit a good solution.

Fortunately, this is solvable, as long as you are willing to change the API. You just need to push the responsibility for allocating space for the data structure to the caller. This will require a change to the API.

Fortunately such a change to the API should be workable. The extra requirements it imposes on the caller are ones that can be discharged by the caller (but cannot be discharged by your library). So, this should work fine, and won't require malloc. Your current API requires the caller to know a constant upper bound on the size of the window. (Why? To allocate space for the buffer without using malloc, the caller needs to know an upper bound on the maximum possible size of buffer that could be needed in any execution, so it can statically allocate that much space.) This means that it will be feasible to solve the problem. Since the caller knows a constant upper bound for the window size, they can allocate space for a larger data structure. If the caller can allocate $k$ words for the buffer, they can just as easily allocate $2k$ words, and that will be enough.

In particular, I suggest you have them allocate twice as much space as your current API requires. This will be enough for you to store the data in a priority queue. In particular, I suggest a data structure that has two parts: a priority queue of all items in the window; and a circular buffer of all items in the window, in the order they appeared in the stream.

At each time step, compute the minimum value within the window using find-min on the priority queue, use the circular buffer to identify the item that is leaving the window, delete that from the priority queue, and insert to add the item that is entering the window. You could use a heap, which supports these operations in logarithmic time. The heap/priority queue can consist of indices into the circular buffer.

With this approach, if the window size is $k$, then the space requirement is $2k$ words of space -- twice as much as you have currently allocated. In fact, you can reduce this further; it suffices to have $k$ words to hold the ints/flots, plus another $k$ $\lceil \lg k \rceil$-bit words for the priority queue.

It's tempting to think that a heap would meet your needs, but it doesn't, because in each time step we need to know both the element that is entering the window and the element that is leaving the window, and it requires extra space to keep track of that.

So, if you want to avoid memory allocations and you want efficient data structures, change the API so that the caller pre-allocates more space for your library.