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:
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.