Need a queue in C

Discussion in 'C Programming' started by ern, Jan 13, 2006.

  1. ern

    ern Guest

    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,
     
    ern, Jan 13, 2006
    #1
    1. Advertisements

  2. ern

    Logan Shaw Guest

    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
     
    Logan Shaw, Jan 13, 2006
    #2
    1. Advertisements

  3. ern

    Nelu Guest

    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. :)
     
    Nelu, Jan 13, 2006
    #3
  4. ern

    ern Guest

    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.
    Wouldn't you just create a data structure that doesn't have variable
    size to avoid this?
    What would that data structure look like? It doesn't really help to
    say "very simple data structure."
    yeah... i know that much...
     
    ern, Jan 13, 2006
    #4
  5. ern

    ern Guest

    What would a circular array queue look like ?

    It's not an assignment !!! arghhhhhh
     
    ern, Jan 13, 2006
    #5
  6. ern

    Default User Guest

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

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



    Brian
     
    Default User, Jan 13, 2006
    #6
  7. ern

    gooch Guest

    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.
     
    gooch, Jan 14, 2006
    #7
  8. ern

    Nelu Guest

    <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.
     
    Nelu, Jan 14, 2006
    #8
  9. ern

    Chuck F. Guest

    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/>
     
    Chuck F., Jan 14, 2006
    #9
  10. ern

    Logan Shaw Guest

    Well, neither does Fortran or Smalltalk -- does that make it a Fortran
    question as well? :)
    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
     
    Logan Shaw, Jan 14, 2006
    #10
  11. ern

    Netocrat Guest

    ]
    There's a kosher alternative:

    static double history[SIZE] = {0};
     
    Netocrat, Jan 14, 2006
    #11
  12. Chuck F. said:
    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, Jan 14, 2006
    #12
  13. ern

    Neil Kurzman Guest

    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.
     
    Neil Kurzman, Jan 14, 2006
    #13
  14. ern

    ern Guest

    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 !
     
    ern, Jan 17, 2006
    #14
  15. ern a écrit :
    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.
     
    Emmanuel Delahaye, Jan 21, 2006
    #15
  16. Chuck F. a écrit :
    Yes, it is.
    Since when ?

    static double history[SIZE] = 0;

    is not

    memset (history, 0, sizeof history);
     
    Emmanuel Delahaye, Jan 21, 2006
    #16
  17. ern

    ern Guest

    If it's not a C question, then what type of question is it ?
     
    ern, Feb 1, 2006
    #17
  18. 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
     
    Vladimir S. Oka, Feb 1, 2006
    #18
  19. Vladimir S. Oka a écrit :
    Yes, sorry for the frenchism...
     
    Emmanuel Delahaye, Feb 1, 2006
    #19
  20. 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
     
    Vladimir S. Oka, Feb 2, 2006
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.