Offer optimised algorithm to work with timestamped values [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

C#. Need to op开发者_StackOverflowtimise counting positive and negative values

I need to maximize speed of the following functionality:

• a. a value comes in. value has 2 properties - int value and long timestamp in ticks.
• b. need to count previously stored values which are younger than 1ms (from the current).
• c. need to count negative and positive separately.
• d. i only need to know if there are either 10 neg or pos values. i dont need to keep any other knowledge of the values.

me thinks - to implement 2 ring arrays for pos and neg separately, replacing expired with 0 keeping track of pos.neg counts as they come.

any thoughts?

---

Maintaining 2 buffers to keep the positives separated from the negatives sounds like a pain and inefficient.

You could instead have a single buffer with all the values, and use std::accumulate to count up the positives and negatives. If you start with a collection of all the tuples (each of which has an age and a value), you could begin by sorting the collection according to age, finding the last element that is <= 1 ms old, and then using accumulate from begin() to that point. Here's some code that demonstrates that last bit:

#include <algorithm>
#include <numeric>
#include <iterator>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

struct Counter 
{
    Counter(unsigned pos=0, unsigned neg=0) : pos_(pos), neg_(neg) {};
    unsigned pos_, neg_;
    Counter& operator+(int n)
    {
        if( n < 0 )
            ++neg_;
        else if( n > 0 )
            ++pos_;
        return * this;
    }
};

int main()
{
    srand((unsigned)time(0));

    vector<int> vals;
    generate_n(back_inserter(vals), 1000, []() 
    {
        return (rand() / (RAND_MAX/40)) - 20;
    });

    Counter cnt = accumulate(vals.begin(), vals.end(), Counter());
}

If sorting the collection by age and then searching the sorted results for the last eligible entry sounds too ineficient, you could use for_each_if instead of accumulate and simply iterate over the whole collection once. for_each_if isn't part of the Standard Library, but it's easy enough to write. If you don't want to muck about with writing your own for_each_if that's fine, too. You could simply tweak the accumulator a bit so that it doesn't accumulate elements which are too old:

#include <algorithm>

#include <numeric>
#include <iterator>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

struct Tuple
{
    int val_;
    unsigned age_;
};

struct Counter 
{
    Counter(unsigned pos=0, unsigned neg=0) : pos_(pos), neg_(neg) {};
    unsigned pos_, neg_;
    Counter& operator+(const Tuple& tuple)
    {
        if( tuple.age_ > 1 )
            return * this; 

        if( tuple.val_ < 0 )
            ++neg_;
        else if( tuple.val_ > 0 )
            ++pos_;

        return * this;
    }
};

int main()
{
    srand((unsigned)time(0));

    vector<Tuple> tuples;
    generate_n(back_inserter(tuples), 1000, []() -> Tuple
    {
        Tuple retval;
        retval.val_ = (rand() / (RAND_MAX/40)) - 20;
        retval.age_ = (rand() / (RAND_MAX/5));
        return retval;
    });

    Counter cnt = accumulate(tuples.begin(), tuples.end(), Counter());
}

---

I would store the values in a min-heap keyed by timestamp - so the youngest values are at the top of the heap. The integer value is auxiliary data at each node. You could then implement the counting with a recursive function that traverses the heap. You'd pass the running total of negative and positive back up the recursive call.

It would look something like this, in Python-like pseudocode with types:

def young_pos_and_neg(Time currtime, HeapNode p):
    if (p is not None and currtime - p.time < 1):
        posleft, negleft = young_pos_and_neg(p.leftChild())
        posright, negright = young_pos_and_neg(p.rightChild())
        totpos = posleft + posright
        totneg = negleft + negright
        if (p.intValue < 0):
            return totpos, totneg + 1
        else:
            return totpos + 1, totneg
    else:
        return 0, 0

If you call this on the heap root before inserting the new value - but with the new value's timestamp as the currtime argument - you will get a count of each. It may not be the fastest possible way, but it's pretty simple and elegant. In C++ you could replace the tuple return value with a struct.