467,161 Members | 1,014 Online

# Need a queue in C

 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, Jan 13 '06 #1
• viewed: 5902
Share:
19 Replies
 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 Jan 13 '06 #2
 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... Jan 13 '06 #3
 On 2006-01-13, Logan Shaw 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...) Jan 13 '06 #4
 What would a circular array queue look like ? It's not an assignment !!! arghhhhhh Jan 13 '06 #5
 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 Jan 14 '06 #6
 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. Jan 14 '06 #7
 ern wrote: What would a circular array queue look like ? It's not an assignment !!! arghhhhhh 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 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...) Jan 14 '06 #8
 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: Jan 14 '06 #9
 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 Jan 14 '06 #10
 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 Jan 14 '06 #11
 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) Jan 14 '06 #12
 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. Jan 14 '06 #13
 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 ! Jan 17 '06 #14
 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 Jan 21 '06 #15
 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 Jan 21 '06 #16
 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 ? Feb 1 '06 #17
 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 Feb 1 '06 #18
 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 Feb 1 '06 #19
 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." Feb 2 '06 #20

### This discussion thread is closed

Replies have been disabled for this discussion.