Need a queue in C

[ern]

I need a FIFO queue of size 20, to keep track of a running average.
Once the queue is full with 20 values, I want to take the sum/20 =
AVERAGE. Then when a new value comes in, I want:

(Old Sum - oldest value + newest value)/20 = New Average

Anybody know an efficient way to implement that? Is a queue even the
best way?

Thanks,

[Logan Shaw]

ern wrote:

I need a FIFO queue of size 20, to keep track of a running average.
Once the queue is full with 20 values, I want to take the sum/20 =
AVERAGE. Then when a new value comes in, I want:

(Old Sum - oldest value + newest value)/20 = New Average

Anybody know an efficient way to implement that? Is a queue even the
best way?

This doesn't really seem like a C question, since the question would
be the same for just about any programming language. It sounds more
like a data structures and algorithms question. Or maybe a homework
question.

Having said that, I wouldn't use a queue for this unless you have a
queue implementation already done that you can use. The reason is,
since it has a fixed size known at compile time, you don't need to
handle the complexity of having a data structure that can have a
variable number of values in it.

Therefore, I would use a very simple data structure and I would have
a statement in my program that looks like this:

index = (index + 1) % 20;

- Logan

[ern]

Logan Shaw wrote:

This doesn't really seem like a C question, since the question would
be the same for just about any programming language. It sounds more
like a data structures and algorithms question. Or maybe a homework
question.
uhhh... it kind of IS a C question since C doesn't support std::queue.
It's not a homework question... it's actually more of an embedded
systems question, since I'm taking values of floating point current
(analog -> digital). The values are fluctuating, so I need to
implement something to stabilize the output. Right now, I'm using
qsort and taking the median. This is working great, but it's slowing
down my application a lot.
since it has a fixed size known at compile time, you don't need to
handle the complexity of having a data structure that can have a
variable number of values in it.
Wouldn't you just create a data structure that doesn't have variable
size to avoid this?
Therefore, I would use a very simple data structure and I would have
a statement in my program that looks like this:
What would that data structure look like? It doesn't really help to
say "very simple data structure."
index = (index + 1) % 20;

yeah... i know that much...

[Nelu]

On 2006-01-13, Logan Shaw <ls**********@a ustin.rr.com> wrote:

ern wrote:

I need a FIFO queue of size 20, to keep track of a running average.
Once the queue is full with 20 values, I want to take the sum/20 =
AVERAGE. Then when a new value comes in, I want:

Therefore, I would use a very simple data structure and I would have
a statement in my program that looks like this:

index = (index + 1) % 20;

This looks similar to a circular array queue.
A queue doesn't have to be implemented using dynamic allocation
does it?
Then again, maybe this is an assignment and ern needs dynamic
allocation. :-)

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

[ern]

What would a circular array queue look like ?

It's not an assignment !!! arghhhhhh

[Default User]

ern wrote:

I need a FIFO queue of size 20, to keep track of a running average.
Once the queue is full with 20 values, I want to take the sum/20 =
AVERAGE. Then when a new value comes in, I want:

You might want to look at what's available here.

http://c.snippets.org/browser.php

Brian

[gooch]

ern wrote:

I need a FIFO queue of size 20, to keep track of a running average.
Once the queue is full with 20 values, I want to take the sum/20 =
AVERAGE. Then when a new value comes in, I want:

(Old Sum - oldest value + newest value)/20 = New Average

Anybody know an efficient way to implement that? Is a queue even the
best way?

Thanks,

This is not really a c question other than that happens to be the
language you are using but Iwould probably just use an array of 20
elements and maintain the index to the oldest element:

//pseudocode
//some initialization stuff comes first
sum = sum - array[oldest element] + new value
average = sum / array size

array[oldest element] = new value

if oldest element is not last element
oldest element++
else
oldest element = 0

Keep in mind this is off the top of my head and is not c code. The c
code to do this should be straight forward and not much different than
my psuedocode with some additional setup and storing the right
variables in the right places but the best way for you to do that for
maximum performance really depends on your system, i.e. maybe you have
some HW registers you can use or something like that.

[Nelu]

ern wrote:

What would a circular array queue look like ?

It's not an assignment !!! arghhhhhh

<OT>
It seems that I missed your post on my default server.
I saw it on a different server at work. I'm now curios to
see whether it will eventually show up on the default
server
</OT>

I learned about it as a "circular array queue", or "queue implemented
using a circular array". I also found it under the name of "circular queue".
It's, basically, a way to implement fixed length queues using arrays (not
only fixed length, but it's usually used when either the number of total
elements is small or you know that you will fill a large part of it all
the time
otherwise it can be a waste of space, if you have no idea how many objects
you can have in the queue at any given time).

A circular array is the one where the first element follows the last
element and
a position is calculated using modulo size of queue. You need two pointers
(meaning indices, not real pointers) to indicate the position of the
head and of
the tail. The problem is determining when the queue is empty and when it's
full as both cases would be indicated by both head and tail indices
pointing to
the same position in the array. This is solved either by using an extra
element
in the array or by keeping a counter. I was taught that the "right" way
to do it is
to keep an extra element in the queue, though the counter implementation
may faster to write. It's not difficult to implement in either cases.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

[Chuck F.]

ern wrote:

I need a FIFO queue of size 20, to keep track of a running
average. Once the queue is full with 20 values, I want to take
the sum/20 = AVERAGE. Then when a new value comes in, I want:

(Old Sum - oldest value + newest value)/20 = New Average

Anybody know an efficient way to implement that? Is a queue
even the best way?

After seeing the thread, the following (untested) code may help:

#define SIZE 20

double movingavg(doubl e newvalue)
{
static double sum = 0.0;
static int index = 0;
static double history[SIZE] = 0;
static int full = 0;

sum -= history[index];
sum += (history[index++] = newvalue);
if (index >= SIZE) {
index -= SIZE;
full = 1;
}
if (full) return sum / SIZE;
else return sum / index;
}

The initialization of the static values is crucial. This is not
quite kosher since it assumes all bits 0 represents a double 0.0.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>

[Logan Shaw]

ern wrote:

Logan Shaw wrote:

This doesn't really seem like a C question, since the question would
be the same for just about any programming language. It sounds more
like a data structures and algorithms question. Or maybe a homework
question.
uhhh... it kind of IS a C question since C doesn't support std::queue.

Well, neither does Fortran or Smalltalk -- does that make it a Fortran
question as well? :-)
It's not a homework question... it's actually more of an embedded
systems question, since I'm taking values of floating point current
(analog -> digital). The values are fluctuating, so I need to
implement something to stabilize the output.

Ah, I've run into that problem on Palm OS before, where the digitizer
(for the pen input) is noisy: if I don't filter it out, it makes it
appear to the user that the pen is jumping around the screen slightly,
which is bad.

In my case, I found I don't actually need an array. I just did a
weighted average. If you are just trying to do a running average
of one value, it would look somewhat like this:

float noisy, averaged;

noisy = get_voltage ();
averaged = noisy;

while (1)
{
noisy = get_voltage ();
averaged = (averaged * 7 + noisy) / 8;

display_voltage (averaged);
}

Note that there is one possible problem here: it's not guaranteed for
sure that the average will converge on all possible values because of
round-off error. With floating point (depending on the actual data
you see), this probably won't be a real problem, although it can be with
integer data. (Think of what happens with integers if get_voltage()
returns 10 the first time and then 11 every time after that.) But
even with integers, the round-off problem can be overcome.

- Logan