Hi Robert,
I'm not going to defend the algorithm (it's a while since I implemented
it). But it does work. It keeps a history of certain peaks, which makes
it efficient to drop them off the end.
Ross.
On 19/07/2016 7:24 AM, robert bristow-johnson wrote:
hi Ross,
i just now saw this reference. never knew of it before. i downloaded
it and took my first cursory look at it.
i have to admit that i am skeptical of O(1), even though i haven't
gotten the complete gist of the article. it says that there are 3
comparisons made per element. i cannot possibly see how it can be
anything that isn't an increasing function of the window length, w.
every element in the array has to be verified as not being the max.
otherwise you have to track the 2nd-place max and the 3rd-place max, ad
arraylengthum. the best you can keep track of w elements is something
O(log2(w)). below is a code snippet that does this. it comes from some
"maxtree" algorithm that i can't remember from who.
now, if the window length w is about 2^30 or a billion, there could be
millions of isolated peaks to keep track of once the maximum falls offa
the edge in the buffer. even if all the peaks are in a sorted list i
just cannot fathom how an algorithm can guarantee it has the max without
a search through that list. and the shortest way to do that is with a
binary tree, but when each new element comes in, you only need to
compare one element per "generation" (an element and its adjacent
neighbor are siblings and everybody has a parent). and there are
O(log2(w)) generations in a binary tree.
this sorta reminds me of an earlier time i was skeptical of this
"zero-delay feedback" notion.
i'll try to understand this paper, but i have this biased skepticism. i
just can't see how it can possibly be better than O(log2(w)).
:-\
r b-j
---------------------------- Original Message ----------------------------
Subject: Re: [music-dsp] highly optimised variable rms and more
From: "Ross Bencina" <rossb-li...@audiomulch.com>
Date: Mon, July 18, 2016 10:52 am
To: music-dsp@music.columbia.edu
--------------------------------------------------------------------------
On 19/07/2016 12:29 AM, Ethan Fenn wrote:
a $ b = max(|a|, |b|)
which I think is what you mean when you describe the peak hold meter.
Certainly an interesting application! And one where I don't think
anything analogous to the Tito method will work.
I've posted here before that there is an O(1) algorithm for running min
and max:
Daniel Lemire, Streaming Maximum-Minimum Filter Using No More than Three
Comparisons per Element, Nordic Journal of Computing, Volume 13, Number
4, pages 328-339, 2006
http://arxiv.org/abs/cs/0610046
Cheers,
Ross.
_______________________________________________
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp
--
r b-j r...@audioimagination.com
"Imagination is more important than knowledge."
#define A_REALLY_LARGE_NUMBER 1.0e20
typedef struct
{
unsigned long filter_length; // array_size/2 < filter_length
<= array_size
unsigned long array_size; // must be power of 2 for this
simple implementation
unsigned long input_index; // the actual sample placement
is at (array_size + input_index);
float* big_array_base; // the big array is malloc()
separately and is actually twice array_size;
} search_tree_array_data;
void initSearchArray(unsigned long filter_length,
search_tree_array_data* array_data)
{
array_data->filter_length = filter_length;
array_data->array_size = 1;
filter_length--;
while (filter_length > 0)
{
array_data->array_size <<= 1;
filter_length >>= 1;
}
// array_size is a power of 2 such that
// filter_length <= array_size < 2*filter_length
// array_size = 2^ceil(log2(filter_length)) =
2^(1+floor(filter_length-1))
array_data->input_index = 0;
array_data->big_array_base =
(float*)malloc(sizeof(float)*2*array_data->array_size); // dunno
what to do if malloc() fails.
for (unsigned long n=0; n<2*array_data->array_size; n++)
{
array_data->big_array_base[n] = -A_REALLY_LARGE_NUMBER;
// init array.
} //
array_base[0] is never used.
}
/*
* findMaxSample(new_sample, &array_data) will place new_sample into
the circular
* buffer in the latter half of the array pointed to by
array_data.big_array_base .
* it will then compare the value in new_sample to its "sibling"
value, takes the
* greater of the two and then pops up one generation to the parent
node where
* this parent also has a sibling and repeats the process. since the
other parent
* nodes already have the max value of the two child nodes, when
getting to the
* top-level parent node, this node will have the maximum value of all
the samples
* in the big_array. the number of iterations of this loop is
ceil(log2(filter_length)).
*/
float findMaxSample(float value, search_tree_array_data* array_data)
{
register float* big_array = array_data->big_array_base;
register unsigned long index = array_data->array_size +
array_data->input_index; // our main buffer is in the latter half
of the big array.
while (index > 1UL)
{
big_array[index] = value;
register float sibling_value = big_array[index ^ 1UL]; //
the upper bits of the sibling address are the same.
if (value < sibling_value)
{
value = sibling_value; // use maximum
of the two values
}
index >>= 1; // parent
address is index/2 (drop remainder or "sibling bit")
}
array_data->input_index++;
if (array_data->input_index >= array_data->filter_length)
{
array_data->input_index = 0;
}
return value;
}
_______________________________________________
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
