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**********@austin.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(double 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.com, 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

[Netocrat]

On Sat, 14 Jan 2006 00:08:17 -0500, Chuck F. wrote:
[...]

static double history[SIZE] = 0; [...] This is not quite kosher since it assumes all bits 0 represents a double
0.0.

There's a kosher alternative:

static double history[SIZE] = {0};

--
http://members.dodo.com.au/~netocrat

[Richard Heathfield]

Chuck F. said:

#define SIZE 20

double movingavg(double 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.

It's true that the code isn't kosher, but that isn't the reason.

In your code, sum gets 0.0 (a double), index gets 0 (an int), full gets 0
(an int), and history gets a syntax error. When you fix it to:

static double history[SIZE] = {0};

history is filled with doubles, each with the value 0.0.

This is because of the guarantee in the Standard that, "If an object that
has static storage duration is not initialized explicitly, it is
initialized implicitly as if every member that has arithmetic type were
assigned 0 and every member that has pointer type were assigned a null
pointer constant."

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Neil Kurzman]

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,

create the buffer
create a pointer to the buffer. Set it to 0
crate the variable Sum set it to 0
collect your 20 samples. Add each new sample to sum

Now on the next sample
1. Add it to sum
2. inc the pointer if it >= 20 set it to 0 ( or do %20)
3. subtract what the pointer is pointing at from Sum.
4. divide by 20.

I hope I got it right But the method is subtract the oldest sample.
that means Sum has the other 19
Add the new and you do not need 20 adds. the circular buffer saves 19
moves.

Anyway I am now off topic. Like the question.

[ern]

Thanks to all who gave me feedback. Now I no longer have to use qsort.
I will require less samples per output, and I can slow the rate of
entry to my sample thread. This will likely speed up my application 3
fold. I'll let you know how it turns out... Thanks !

[Emmanuel Delahaye]

ern a écrit :

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?

Please define 'efficient way' and 'best way'. There are different ways
to achieve your goal (array, list), but it's not really a C-language
question. It's more a design issue.

--
A+

Emmanuel Delahaye

[Emmanuel Delahaye]

Chuck F. a écrit :

static double history[SIZE] = 0; This is not quite
kosher
Yes, it is.
since it assumes all bits 0 represents a double 0.0.

Since when ?

static double history[SIZE] = 0;

is not

memset (history, 0, sizeof history);

--
A+

Emmanuel Delahaye

[ern]

Emmanuel Delahaye wrote:

ern a écrit :

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?

Please define 'efficient way' and 'best way'. There are different ways
to achieve your goal (array, list), but it's not really a C-language
question. It's more a design issue.

--
A+

Emmanuel Delahaye

If it's not a C question, then what type of question is it ?

[Vladimir S. Oka]

ern wrote:

Emmanuel Delahaye wrote:

ern a écrit :

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?

Please define 'efficient way' and 'best way'. There are different ways
to achieve your goal (array, list), but it's not really a C-language
question. It's more a design issue.

--
A+

Emmanuel Delahaye

If it's not a C question, then what type of question is it ?

You cannot be serious!

Point to a thing in your original post that makes it a question about,
or even involving, C programming language. FWIW, you may have wanted to
implement this using pen and paper.

Emmanuel is also quite right to as about `efficient` and `best`. Did
you mean /memory/ efficient, /time/ efficient, /cost/ efficient, or
something else altogether? Also, there rarely is `the best` way of
doing anything, and more or less the same questions apply: best in what
area?

IMHO, Emmanuel was also dead on the money when he told you that your
question is "more [of] a design issue".

Cheers

Vladimir

[Emmanuel Delahaye]

Vladimir S. Oka a écrit :

IMHO, Emmanuel was also dead on the money when he told you that your
question is "more [of] a design issue".

Yes, sorry for the frenchism...

--
A+

Emmanuel Delahaye

[Vladimir S. Oka]

Emmanuel Delahaye wrote:

Vladimir S. Oka a écrit :

IMHO, Emmanuel was also dead on the money when he told you that your
question is "more [of] a design issue".

Yes, sorry for the frenchism...

No, in retrospect, I'm sorry for being picky about /natural/ language. I
guess my translator alter-ego can't keep its ugly head down
sometimes. ;-)

(BTW, in /my/ first language there'd be no "of" either.)

Cheers

Vladimir

--
"Matrimony isn't a word, it's a sentence."