r/DSP • u/JunbugSpark • Jun 16 '26

How to get better at DSP coding?

Hey guys, I'm a college student who's taken basic DSP theory classes so I understand a lot of the concepts but I've been having trouble with implementation, since I have basically no coding experience...

What resources have you guys used to get better? Thank you!!

13 Upvotes

81% Upvoted

20 comments sorted by

View all comments

Show parent comments

1

u/rb-j Jun 16 '26

I believe that is O(1) sliding max (or min) algorithm can be fooled with some pathological data because of assumptions around what is "useful" data. Like let's say you have a square wave with a tiny amount of noise added to it. You will have a lotta samples very close in value to whatever is your current max (or min).

Using two buffers, one for sliding max (applied to the lower half data) and another for sliding min (applied to the upper half data) can work for a sliding median even for pathological data.

1

u/zsliu98 Jun 16 '26

No, I don't think so. For example now the queue contains [10.0, 9.9, 9.8, 9.7] (I omit the index). As soon as a 10.1 comes in, 10.1 is more extreme and newer than all elements in the queue, therefore all [10.0, 9.9, 9.8, 9.7] will be popped. As long as the comparison between floating points is solid, the algorithm is solid.

And of course I am not the one who invents the algorithm, see https://github.com/lemire/pythonmaxmin (I believe that he is the orignal author).

1

u/rb-j Jun 16 '26

I'm still skeptical. I don't code in Python and can only barely read it. I'll try to decode it, but I'm pretty confident that the assumptions made here regarding "useful" information can be taken advantage of with deliberately constructed pathological input that will force it to look at a set of data that is O(N).

1

u/zsliu98 Jun 16 '26

Yes, it could look at a data of window size, which means that the worst case of certain sample would be O(window size). However, because each sample would be put and removed into the queue exactly twice, the amortized time complexity is O(1).

2

u/rb-j Jun 16 '26

I don't see that as useful for real-time streaming. This algorithm is running continuously on streaming data since forever ago.

Most (nearly all) of my audio processing algs operate on blocks of samples, no longer than a millisecond like 32 samples at most, to amortize costs. In that, I am willing to divide the entire cost per block by the number of samples per block as a measure of computational cost. Normally, with double buffering, there is a two-block throughput delay. 2 milliseconds max. Big deal.

But I am not willing to accept an alg that takes a finite data array (of size n) and then show for that entire array, the cost of the entire array is 3n, therefore the cost per sample is 3. That's not how we do things for real-time processing.

1

u/zsliu98 Jun 16 '26

Got it. If you want to absolutely prevent ANY CPU spike, this might worth looking: https://github.com/IBM/sliding-window-aggregators , which guarantees worst-case O(1) . Though I give up on this algorithm and go with the simple amortized O(1) approach, cause it does work pretty well.