1
$\begingroup$

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}.
$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ IIUC, your priority queue idea requires the leaving element to be looked up before deletion, which heaps can't do in log time. (BSTs can, but need space for pointers.) Also it seems this would rearrange the input array (which seems reasonable under the space constraints). Finally I don't see why copying an iterator would be an issue? $\endgroup$ Jun 11, 2021 at 23:07
  • $\begingroup$ @j_random_hacker, hence why this question mentions that this can be done with two iterators but not with one. You can do it with an extra field in each heap node that's a linked list through items in the order they leave, but that requires extra space, hence my recommendation to change the API. It's not copying an iterator; the second iterator needs to be delayed, so the natural way to implement the second iterator involves saving the last $k$ items (where $k$ is the window size) which effectively adds to the space requirements. $\endgroup$
    – D.W.
    Jun 12, 2021 at 0:43
  • $\begingroup$ So, that's the thing, I can't use more space, not because of lack of wanting to, but some embedded environments that I wish to target may not even have a heap (as in "allocate on the heap") or even malloc available! $\endgroup$ Jun 12, 2021 at 1:23
  • $\begingroup$ @MarkLeMoine, I know, but what you want to do requires more space. Fortunately, this can be achieved without dynamic memory allocation by changing the API. Your API requires the window size to have a fixed upper bound that is known to the caller (so that the caller can allocate space for it). If the caller can statically allocate space for the window, it can also allocate twice as much space, as that also will have a fixed upper bound that is known to the caller. It won't require malloc, it'll just require pushing the responsibility to statically allocate enough space to the caller. $\endgroup$
    – D.W.
    Jun 12, 2021 at 1:31
  • $\begingroup$ "hence why this question mentions that this can be done with two iterators but not with one" -- I don't see this mentioned anywhere in the OP's question? Regarding iterators, it seems to me that the top-level function could return an iterator that internally consists of the two iterators you mention, plus, e.g., an integer field counting down the number of steps remaining before the deletion iterator should begin. $\endgroup$ Jun 12, 2021 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.