Forum Rule: Always post complete source code & details to reproduce any issue!
Results 1 to 18 of 18

Thread: How to keep track of biggest value in sliding window

  1. #1
    Senior Member
    Join Date
    Jan 2020
    Posts
    173

    How to keep track of biggest value in sliding window

    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.

  2. #2
    Senior Member
    Join Date
    Dec 2016
    Location
    Montreal, Canada
    Posts
    3,664
    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

  3. #3
    Senior Member
    Join Date
    Jan 2020
    Posts
    173
    I was considering it. What does the max() function do exactly?

  4. #4
    Senior Member
    Join Date
    Dec 2016
    Location
    Montreal, Canada
    Posts
    3,664
    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.

  5. #5
    Senior Member
    Join Date
    May 2017
    Posts
    238
    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.

  6. #6
    Senior Member
    Join Date
    Dec 2016
    Location
    Montreal, Canada
    Posts
    3,664
    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 by tonton81; 02-14-2021 at 06:15 PM.

  7. #7
    Senior Member
    Join Date
    Jan 2020
    Posts
    173
    Quote Originally Posted by tonton81 View Post
    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.

  8. #8
    Senior Member
    Join Date
    Dec 2016
    Location
    Montreal, Canada
    Posts
    3,664
    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 by tonton81; 02-14-2021 at 06:23 PM.

  9. #9
    Senior Member
    Join Date
    Jan 2020
    Posts
    173
    Quote Originally Posted by tonton81 View Post
    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.

  10. #10
    Senior Member
    Join Date
    Dec 2016
    Location
    Montreal, Canada
    Posts
    3,664
    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());
     // queue.clear(); // commented out for rolling window
      sample_refresh = millis();
    }
    Last edited by tonton81; 02-14-2021 at 06:39 PM.

  11. #11
    Senior Member
    Join Date
    Jan 2020
    Posts
    173
    Quote Originally Posted by rcarr View Post
    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?

  12. #12
    Senior Member
    Join Date
    May 2017
    Posts
    238
    Quote Originally Posted by frankzappa View Post
    Is this the explanation to the code I posted above?
    Yes it is.

  13. #13
    Senior Member
    Join Date
    Aug 2013
    Location
    Gothenburg, Sweden
    Posts
    396
    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.

  14. #14
    Senior Member
    Join Date
    Jan 2020
    Posts
    173
    Quote Originally Posted by mlu View Post
    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?

  15. #15
    Senior Member
    Join Date
    Dec 2016
    Location
    Montreal, Canada
    Posts
    3,664
    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

  16. #16
    Senior Member
    Join Date
    Jan 2020
    Posts
    173
    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.

  17. #17
    Senior Member
    Join Date
    Aug 2013
    Location
    Gothenburg, Sweden
    Posts
    396
    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

  18. #18
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany
    Posts
    8,230
    Here is a good article with various methods: https://www.geeksforgeeks.org/slidin...ays-of-size-k/

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •