On 4/09/2016 2:49 AM, robert bristow-johnson wrote:
sorry to have to get to the basics, but there are no *two* length
parameters to this alg. there is only one.
define the streaming real-time input sequence as x[n]. the length of
this signal is infinite.
output of running max alg is y[n]. the length of this signal is
infinite.
which is it?:
y[n] = max{ x[n], x[n-1], x[n-2], ... x[n-N+1] }
or
y[n] = max{ x[n], x[n-1], x[n-2], ... x[n-R+1] }
i've been under the impression it's the first one. using "N". earlier i
had been under the impression that you're processing R samples at a
time, like processing samples in blocks of R samples. now i have no idea.
I agree that Evan's setup is unusual and not what you'd use for
streaming real-time processing.
For what it's worth, in my descriptions of my code:
y[n] = max{ x[n], x[n-1], x[n-2], ... x[n-windowSize+1] }
The history may contain a maximum of windowSize elements (or
windowSize-1 depending on the implementation details).
I don't think I mentioned processing samples in blocks, but I don't
think we can usefully analyse the practical complexity of this algorithm
without discussing block-wise processing.
A worst-case windowSize trimming event (LIFO end of queue) can only
possibly happen every windowSize samples(*). This reduces the worst-case
complexity for most samples in a block. Hence block-based processing
will always (not just on average) yield amortization benefits. If the
block size is larger than the windowSize, the original algorithm will
run in O(1) worst-case time per sample, otherwise it will be O(k) where
k is some function of windowSize and blockSize that I am not prepared to
calculate before coffee.
(*) Because once windowSize samples have been trimmed, it will take
another windowSize input samples before the queue is at maximum capacity
again (and this, only in the decreasing ramp case).
Ross.
_______________________________________________
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp
