| Author |
Message |
zimezum@gmail.com
Guest
|
 Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Max of series of real-time data |
|
|
Hi,
I have a real-time application project for which the following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Is there a quicker way to do this?
Any input is greatly appreciated,
Andras |
|
| Back to top |
|
 |
Bob
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Max of series of real-time data |
|
|
<zimezum@gmail.com> wrote in message
news:1135117052.745749.292580@g14g2000cwa.googlegroups.com...
| Quote: | Hi,
I have a real-time application project for which the following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Is there a quicker way to do this?
Any input is greatly appreciated,
Andras
|
Hi Andras,
Do you have enough RAM to make 2 more arrays? 200uS is plenty of time to do
a block extrema calc. E.g. divide your N by 100 (5000/100 = 50). Keep an
array of 50 "block extrema" - that is, the max for each block of 50 data
points. Now extreme for the current window is the extreme of the 50 block
extrema and the partial blocks at each end (one incoming and one outgoing).
In parallel with your data points is an array of the running extrema
*within* the block. This array (5000 intraBlockExtrema) avoids running
through any individual data points: the extreme of the incoming block is the
current entry in the intraBlockExtrema and the extreme of the outgoing block
is intraBlockExtrema of the point you are about to dump.
I hope that makes sense. I think if you extend it and generalize it, then it
becomes the Skip List that John pointed to. Anyway, with the numbers I used
in the example, with each new data point you only make 3 comparisons. At the
end of each block, you make 50 comparisons. At some other time, you run
through the most recently full block *backwards* (making 100 comparisons)
and store those extrema to use on the outgoing comparison. On average,
around 5 comparisons per data point.
Bob |
|
| Back to top |
|
|
David Tweed
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Max of series of real-time data |
|
|
Jerry Avins wrote:
| Quote: | zimezum@gmail.com wrote:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Of course there is. Keep a variable that holds the largest (or smallest)
value so far, and compare each new sample against it. If the comparison
fails, do nothing. If it succeeds, update the variable.
|
Jerry, you gotta stop shooting from the hip on these.
What do you do when the current maximum (or minimum) value falls
out the other end of the window?
The only answer I can see would involve keeping both a queue of the
data in the window, and a separate copy of the data that's kept in
sorted order.
At each sample time, take the oldest value out of the queue, and
also delete a copy of that value from the sorted buffer (find it
using a binary search, and it doesn't matter if there's more than
one). Then insert the new value into the queue and also into the
sorted buffer, again using a binary search. Take the highest value
(or lowest value, or middle value, etc.) out of the sorted buffer
as the output of your filter.
The real trick is picking the right type of data structure to hold
the sorted data, so that the insertions and deletions themselves
aren't too computationally expensive. Ideally, you'd figure out
where the deletion needs to happen, where the insertion needs to
happen, and only shift the data in the buffer between those two
points.
-- Dave Tweed |
|
| Back to top |
|
|
John Herman
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Max of series of real-time data |
|
|
I think he needs to maintain the value of the maximum over the last few
thousand samples. This is easy to do with skip lists and data pointers on a
small general purpose computer, maybe a PIC. See
http://www.nist.gov/dads/HTML/skiplist.html
or google "skip list".
In article <QLWdnXdK5fe7GDXenZ2dnUVZ_sidnZ2d@rcn.net>, Jerry Avins
<jya@ieee.org> wrote:
| Quote: | zimezum@gmail.com wrote:
Hi,
I have a real-time application project for which the following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Is there a quicker way to do this?
Of course there is. Keep a variable that holds the largest (or smallest)
value so far, and compare each new sample against it. If the comparison
fails, do nothing. If it succeeds, update the variable.
Jerry |
|
|
| Back to top |
|
|
zimezum@gmail.com
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Max of series of real-time data |
|
|
Jerry,
Thank you for your input. One question lingers, though....when the max
data
falls out the window (so to speak) the next largest must be idetified
as the max
unless a larger value entered the window. That is, the algorithm must
have a
'forgetting factor' of some sort which is related to the size of the
window.
Suppose the input stream is a monotomic decreasing one, then all the
values in
the window must be remembered (and their order), so that when the
largest one
is leaving the window the 'max' variable will take the next largest
value, and so on,
until the smallest element is reached.
In this case every element of the window must be remembered and
compared against
the new value entering the window. Sound like a quite complicated
task...
Andras
Jerry Avins wrote:
| Quote: | zimezum@gmail.com wrote:
Hi,
I have a real-time application project for which the following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Is there a quicker way to do this?
Of course there is. Keep a variable that holds the largest (or smallest)
value so far, and compare each new sample against it. If the comparison
fails, do nothing. If it succeeds, update the variable.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Dec 21, 2005 1:16 am Post subject:
Re: Max of series of real-time data |
|
|
zimezum@gmail.com wrote:
| Quote: | Hi,
I have a real-time application project for which the following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Is there a quicker way to do this?
|
Of course there is. Keep a variable that holds the largest (or smallest)
value so far, and compare each new sample against it. If the comparison
fails, do nothing. If it succeeds, update the variable.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
John E. Hadstate
Guest
|
| Posted:
Wed Dec 21, 2005 7:33 am Post subject:
Re: Max of series of real-time data |
|
|
<zimezum@gmail.com> wrote in message
news:1135117052.745749.292580@g14g2000cwa.googlegroups.com...
| Quote: | Hi,
I have a real-time application project for which the
following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of
a series of
data (window) in an input stream from a sensor. The max.
data needs be
updated every sample (5000 Hz samplerate). I need a quick
way of
determining the max. element in the data window (of about
3000 - 5000
samples) without the obviously time-consuming way of
comparing each
element with the next, or quicksorting, due to time
constraints.
Is there a quicker way to do this?
Any input is greatly appreciated,
Andras
|
Assuming that your data is integer and you have enough
memory, here is one way to achieve what you're looking for:
1. Allocate an array of integers that is large enough to
hold the maximum number of different values that your data
can take on. For example, if you have 16-bit data, you need
an array of 64K integers. Each array element needs to be
big enough to count the number of elements in your data
window. An array of unsigned chars will accommodate data
windows of up to 255 points, an array of unsigned shorts
will accommodate data windows of up to 64K-1 points and so
on. Initialize all the elements of this array to zero.
2. Each time a new point is captured:
2a. use the value of the point as an index into the array
allocated above. Increment the array element at that index.
2b. if the value of the point is bigger than the biggest one
previously seen, replace the old biggest value with the new
biggest value.
2c. using the point that just shifted out of the window,
decrement the array element whose index corresponds to that
point's value.
2d. if the value of the point is equal to the largest value
previously seen, and the contents of the array element
indexed by the value of the point is zero, then search
downward to the next array index containing a non-zero
element. This array index will be the new largest value in
the data window.
This algorithm works because the big array holds an
inventory of all the values in the data window. When a new
value is brought in, it is tallied in the inventory. When
it is dropped out, it is removed from the inventory. Only
values with non-zero representation in the inventory are
candidates to be the "biggest" value in the data window, and
then only if there are no other candidates above them in the
inventory. |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Dec 21, 2005 8:32 am Post subject:
Re: Max of series of real-time data |
|
|
zimezum@gmail.com wrote:
| Quote: | Jerry,
Thank you for your input.
|
Too soon for that.
| Quote: | One question lingers, though....when the max data falls out the window ...
|
I hadn't realized the significance of "(window)". Perhaps the
parentheses threw me.
| Quote: | Suppose the input stream is a monotomic decreasing one, then all the
values in
the window must be remembered (and their order), so that when the
largest one
is leaving the window the 'max' variable will take the next largest
value, and so on,
until the smallest element is reached.
In this case every element of the window must be remembered and
compared against
the new value entering the window. Sound like a quite complicated
task...
|
The best I can think of is an insertion sort, done as each sample
arrives. I can see many pitfalls trying to implement it, but maybe there
are ways around some of them if there's enough memory. It won't be
pretty even if it works.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
Jerry Avins
Guest
|
| Posted:
Wed Dec 21, 2005 8:35 am Post subject:
Re: Max of series of real-time data |
|
|
David Tweed wrote:
| Quote: | Jerry Avins wrote:
zimezum@gmail.com wrote:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.
Of course there is. Keep a variable that holds the largest (or smallest)
value so far, and compare each new sample against it. If the comparison
fails, do nothing. If it succeeds, update the variable.
Jerry, you gotta stop shooting from the hip on these.
|
Yup.
| Quote: | What do you do when the current maximum (or minimum) value falls
out the other end of the window?
The only answer I can see would involve keeping both a queue of the
data in the window, and a separate copy of the data that's kept in
sorted order.
At each sample time, take the oldest value out of the queue, and
also delete a copy of that value from the sorted buffer (find it
using a binary search, and it doesn't matter if there's more than
one). Then insert the new value into the queue and also into the
sorted buffer, again using a binary search. Take the highest value
(or lowest value, or middle value, etc.) out of the sorted buffer
as the output of your filter.
The real trick is picking the right type of data structure to hold
the sorted data, so that the insertions and deletions themselves
aren't too computationally expensive. Ideally, you'd figure out
where the deletion needs to happen, where the insertion needs to
happen, and only shift the data in the buffer between those two
points.
|
Another approach might be a time key with each sorted entry. Messy at
best ... until the mental breakthrough.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ |
|
| Back to top |
|
|
zimezum@gmail.com
Guest
|
| Posted:
Wed Dec 21, 2005 9:16 am Post subject:
Re: Max of series of real-time data |
|
|
John,
So far the method you proposed seems easier for me to understand.
I'll give it a try over the next few days.
Some words about the application (so that the others will have a
better idea about what's going on);
- it is a real-time controller for (right now) a pair of magnetic
bearings
in an experimental setting at Auburn University. The h/w is a dSPACE
DS1005 board, which is in fact a PPC750 processor running at 400 MHz.
The main algorithm is a type-2 fuzzy logic controller, which takes up
most of the cycle at the 5 kHz samplerate. The adative adjustment
is still needs to be implemented, so the 200 usec is not available,
it is about 50 usec which I can affor at this point. Memory is not a
problem right now, the board is equipped with 128MB RAM which is
far more than I ever need for this kind of project.
The input sensors are connected to the 16 bit ADC (which can be
adjusted to 14,12, 10 and 8 bits for each channel).
Programming is in C language...I understand that assembly language
would give serious speed boost, but I am afraid of messing up the
proprietary dSPACE functions, interrupts, which is another can of
worms.
Andras |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in