Re: [music-dsp] efficient running max algorithm

[Evan Balster]

Ahh, smart!  Thanks for the insight; I understand now.

It occurs to me that you could slightly tighten the bound on per-sample
work, because it's not necessary to include the elements of the linear
search in the binary one.  The worst-case would then be O(J) per sample,
where J=log2(w-J).  But this is a very marginal improvement and it's
difficult to write out the bound in a clearer way.

– Evan Balster
creator of imitone 

On Thu, Jul 21, 2016 at 7:40 AM, Ethan Fenn  wrote:

> Yeah, with a binary search, you're doing O(log(w)) work, but you might not
> end up discarding any samples. With the paper's linear search, you might do
> O(w) work, but only if you end up discarding O(w) samples. So, it turns out
> to be worth it, as long as you can tolerate the spike.
>
> The thinking with the partial linear search is sure, let's spend O(log(w))
> time doing a binary search, but only if we first confirm we'll be
> discarding at least O(log(w)) samples.
>
> -Ethan
>
>
>
>
> On Wed, Jul 20, 2016 at 6:37 PM, Evan Balster  wrote:
>
>> Ethan ---
>>
>> If we use only a binary search in the discard step, isn't the amortized
>> complexity still O(N)?  I suppose not...  We'd be doing a log2(w) search
>> every sample in the worst case where a monotonic decrease occurs.
>>
>> I'll have to look over the paper to get a better understanding, but would
>> be very interested to hear your thought process with the partial linear
>> search.
>>
>> – Evan Balster
>> creator of imitone 
>>
>> On Wed, Jul 20, 2016 at 1:23 PM, Dan Gillespie <
>> dgilles...@cosineaudio.com> wrote:
>>
>>> Regarding the Lemire paper his code is provided here:
>>> https://github.com/lemire/runningmaxmin
>>>
>>> It's been a while since I've read the paper, but iirc it reports fast
>>> average O(.), not worst case.  Specifically it's good if the signal has few
>>> changes in direction, but the worst case is not better than other
>>> algorithms.
>>>
>>> Dan Gillespie
>>>
>>> ___
>>> dupswapdrop: music-dsp mailing list
>>> music-dsp@music.columbia.edu
>>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>>
>>>
>>
>> ___
>> dupswapdrop: music-dsp mailing list
>> music-dsp@music.columbia.edu
>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>
>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] efficient running max algorithm

[Wen Xue]

The trick is to count the total number of operations, not for each incoming 
sample as the window moves. 

The algorithm maintains a buffer that pushes at the back and pops at both front 
and back. Each sample is pushed onto the buffer and popped out of it exactly 
once. If R samples are popped from the front, then N-R are popped from the 
back. All N pushes are at the back.

Each comparison with an incoming sample leads to either one push or one pop at 
the back. It naturally follows that the total of N-R pops and N pushes at the 
back costs 2N-R comparisons. There are also N yes/no comparisons to determine 
whether to pop a sample from the front as the window moves on.  So yes, the 
total is O(N) regardless of w.

-Xue


From: Ethan Fenn___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] efficient running max algorithm

[Ethan Fenn]

Yeah, with a binary search, you're doing O(log(w)) work, but you might not
end up discarding any samples. With the paper's linear search, you might do
O(w) work, but only if you end up discarding O(w) samples. So, it turns out
to be worth it, as long as you can tolerate the spike.

The thinking with the partial linear search is sure, let's spend O(log(w))
time doing a binary search, but only if we first confirm we'll be
discarding at least O(log(w)) samples.

-Ethan




On Wed, Jul 20, 2016 at 6:37 PM, Evan Balster  wrote:

> Ethan ---
>
> If we use only a binary search in the discard step, isn't the amortized
> complexity still O(N)?  I suppose not...  We'd be doing a log2(w) search
> every sample in the worst case where a monotonic decrease occurs.
>
> I'll have to look over the paper to get a better understanding, but would
> be very interested to hear your thought process with the partial linear
> search.
>
> – Evan Balster
> creator of imitone 
>
> On Wed, Jul 20, 2016 at 1:23 PM, Dan Gillespie  > wrote:
>
>> Regarding the Lemire paper his code is provided here:
>> https://github.com/lemire/runningmaxmin
>>
>> It's been a while since I've read the paper, but iirc it reports fast
>> average O(.), not worst case.  Specifically it's good if the signal has few
>> changes in direction, but the worst case is not better than other
>> algorithms.
>>
>> Dan Gillespie
>>
>> ___
>> dupswapdrop: music-dsp mailing list
>> music-dsp@music.columbia.edu
>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>
>>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

[music-dsp] unsibscribe

[Iain]

 

 

From: music-dsp-boun...@music.columbia.edu 
[mailto:music-dsp-boun...@music.columbia.edu] On Behalf Of Liam Sargent
Sent: 20 July 2016 23:11
To: music-dsp@music.columbia.edu
Subject: [music-dsp] Music applications/DSP online masters

 

Hello all,

 

Been subscribed to this list for a while and have found the conversation 
fascinating. I recently graduated with a B.S. in Computer Science and have a 
strong interest in continuing my education in DSP programming for audio 
applications. I have recently started a full time job in the SF Bay Area as a 
software engineer - will likely have to complete course material online.

 

Wondering anyone on this list has recommendations for a solid online M.S. 
program focused on audio signal processing/music applications, or just 
resources for continuing my learning in general.

 

Liam

___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp