How to keep track of biggest value in sliding window

Status
Not open for further replies.

frankzappa

Well-known member
Hello!

I need guidance on making a function for this:

I need to keep track of the biggest sample in the last ~5ms or so. It needs to update for every new sample that comes in. I'm sampling sensors at 50kHz.

Surely there must be a clever way of doing this other than going through the whole window doing comparisons and whanot.

I found this online, can someone help me understand it:

Code:
There's a good linear time solution to this that requires only one comparison and a couple operations on the end of a list per sample. I'm pretty sure this is as fast as you can get. I don't think anyone has posted it yet, but here it is:


keep a list[L of (sample volume, sample index) pairs



for each sample

  calculate the (volume, index) pair V for the current sample



  if L is empty

    push V onto L



  if L.front().index() is older than your window

    pop L.front() from the list



  while V.volume() > L.back().volume()

    pop L.back()



  push V onto the back of L

  L.front() is the (volume, index) pair of the current loudest sample within your window.

end for loop



Why does this work? As a side effect of the way L is constructed, it is always non-empty and sorted in descending order by both sample volume and ascending order by sample index. Furthermore, no pair will be removed from L until either it is older than your window size, or a louder more recent sample is found. Thus the front of L is always the loudest sample within the size of the window.

How fast is it? Each sample is added to or removed from L at most once. After each comparison, a sample is either added to or removed from L. Therefore, you do at most one comparison, one list addition, and one list removal per sample. As all of those are constant-time operations, the procedure takes time linear on the number of samples.
 
Circular_Buffer can find your largest value, no need to dequeue either if you plan to just keep filling the queue endlessly, oldest values will be overwritten, and you can easily check the biggest value using the max() call
 
it returns the biggest value in the queue of your samples, you also got min() median() average() deviation() and variance()

just be sure the queue is a power of 2. if you want 100 samples, you need a queue of 128.
 
Pretend your keeping the values listed on a piece of paper:

The first value, you simply write that down on the paper and also its index 0

Scenario 1: The values are always increasing: Since it is larger than what you have on the paper, you erase what you have and write the new value and index down.

Scenario 2: The values are always decreasing: You will write down the values and index under the ones you have until you have 5ms worth of numbers.

Scenario 3: The values start increasing: You look at the bottom of the list of numbers and erase all that are less than the new number and when write the new number and index on the paper.

Scenario 4: The first number in the list is too old, you erase that on the paper and now the highest number is on the 2nd line on the paper.
 
actually, depending if you want it samples over time, (posted above), or biggest number of all:
Code:
static uint32 sample_refresh = millis();
if ( millis() - sample_refresh >=  5 ) { // 5ms
  Serial.print("This is the biggest sample in last 5ms..: ");
  Serial.println(old_sample);
  old_sample = 0;
  sample_refresh = millis();
}

if (new_sample > old_sample ) old_sample = new_sample; // take a new sample here

for the Circular_Buffer version, for a 5ms sample, just .clear() the buffer every 5ms while your other code is dropping samples inside and check with max() every 5 ms. Probably cleaner than above code.

Code:
queue.write(sample); //take samples

static uint32 sample_refresh = millis();
if ( millis() - sample_refresh >=  5 ) { // 5ms
  Serial.print("This is the biggest sample in last 5ms..: ");
  Serial.println(queue.max());
  queue.clear();
  sample_refresh = millis();
}
 
Last edited:
actually, depending if you want it samples over time, (posted above), or biggest number of all:
Code:
if (new_sample > old_sample ) old_sample = new_sample;

I want the biggest number that is inside the current window. The window constantly changes as new samples come in. The max() function would do exactly what I want as long as I keep the buffer at a size of 250 which corresponds to 5ms.

However I'm thinking that there must be a more efficient way because I need to do some other processing as well and I have to do it while waiting for the next sample to finish.

Must be some way to sort the sample velocities in descending order and also keep track of when they expire.
 
i edited the post above, typing it from my phone so... :)
250 size buffer would be 256, filling it completely is not mandatory but must always be power of 2 (example, 300 byte buffer needs a queue size of 512)

if you are worried about latency in your other code, check out timer interrupts or teensythreads and take samples from the interrupt or thread context
 
Last edited:
i edited the post above, typing it from my phone so... :)

Thanks but that's not what I want to do. I need the biggest value in a sliding window of 250 samples (5ms). The window is moving one sample every time a new sample comes in. The example you showed is stationary and would add a delay of 5ms.

Also I don't necessarily need a clean way, I need an efficient way. A clean way would be to call max() but I'm trying to find a faster way.
 
okay then, remove the .clear() from the 2nd posted code, that window will now be moving (not stationary), with the oldest sample going off grid when newest sample is added :)

Code:
queue.write(sample); //take samples

static uint32 sample_refresh = millis();
if ( millis() - sample_refresh >=  5 ) { // 5ms
  Serial.print("This is the biggest sample in last 5ms..: ");
  Serial.println(queue.max());
[COLOR="#FFA07A"] // queue.clear(); // commented out for rolling window[/COLOR]
  sample_refresh = millis();
}
 
Last edited:
Pretend your keeping the values listed on a piece of paper:

The first value, you simply write that down on the paper and also its index 0

Scenario 1: The values are always increasing: Since it is larger than what you have on the paper, you erase what you have and write the new value and index down.

Scenario 2: The values are always decreasing: You will write down the values and index under the ones you have until you have 5ms worth of numbers.

Scenario 3: The values start increasing: You look at the bottom of the list of numbers and erase all that are less than the new number and when write the new number and index on the paper.

Scenario 4: The first number in the list is too old, you erase that on the paper and now the highest number is on the 2nd line on the paper.

Is this the explanation to the code I posted above?
 
The key to understanding the algorithm are the following properties of the list L of (sample volume, sample index) pairs

* L is always sorted by increasing sample index/sample time since we only append at the end, and remove from the front

* L only contains elements from our current sample window, we remove any to old values from the front and add the new sample at the back

* The elements in L are always descending in volume so the max value is found at the front. This happens because we remove any smaller, or equal, values from the back before inserting the newly inserted element at the back, so it will be will be smaller than the elements already in the list, keeping the descending property intact. For instance if the new value is very small it is inserted at the back, and then removed when a larger value comes along. If the new value to add is large, bigger than current max, then all elements will be removed and the new element inserted as the only element in the list.

This means that the list L contains a decreasing sequence of elements from the sample window starting at the max. Any increasing subsequence is removed by the removals of small values at the insertion stage.
 
The key to understanding the algorithm are the following properties of the list L of (sample volume, sample index) pairs

* L is always sorted by increasing sample index/sample time since we only append at the end, and remove from the front

* L only contains elements from our current sample window, we remove any to old values from the front and add the new sample at the back

* The elements in L are always descending in volume so the max value is found at the front. This happens because we remove any smaller, or equal, values from the back before inserting the newly inserted element at the back, so it will be will be smaller than the elements already in the list, keeping the descending property intact. For instance if the new value is very small it is inserted at the back, and then removed when a larger value comes along. If the new value to add is large, bigger than current max, then all elements will be removed and the new element inserted as the only element in the list.

This means that the list L contains a decreasing sequence of elements from the sample window starting at the max. Any increasing subsequence is removed by the removals of small values at the insertion stage.

This seems like the way to go.

It’s completely clear now. If the value to be inserted is bigger than max it will delete everything. I thought this would be a problem but since it is the newest value it doesn’t matter because it will stay in the list longer than any current value anyway.

Thanks.

What about the size of the list L? It seems it will be dynamic but never bigger than the number of samples in the window?
 
thats not a sliding window then, thats going back to static window again, and you'd then have to repopulate the list, which now has 1 value to start with :)
 
I don’t think so. You need to keep track of the time of arrival so the list is a pair consisting the value and the time of arrival. You fill in new values as they come in and remove old values when they expire or if they are too small to ever be used. If the newest value is the biggest then you can remove all other values because they can never be used. You only care about the value in the front which is the biggest one.

When the biggest value is too old it is removed and the next value is used.

I think this will work. It’s either this or some kind of envelope with a sample hold function.
 
Its a queue with maximal size equal to sample window, so a ring buffer should work fine. My guess is that on average the length should be something like 2log(N), if the values are a bit randomly distributed
 
Status
Not open for further replies.
Back
Top