Data over Time with Fixed Maximum Length

Get Started
1

Hello,

I have a tricky problem. I want to monitor some data over time, and keep an area which basically gives me the data from when I started, to the current time, but with a limited number of positions.

For example, if the data was 1 through 20, and I had a maximum length of 4, at the end it’d look something like this:
1, 7, 13, 20

(That’s a very small example).

Does anyone have any idea how I can achieve this?

Thanks.

2

Well, I came up with this little algorithm. It’s not ideal, but it’s close. If anyone has anything better, please share:


// pseudo-code
// initialization
Array data = new Array()
int maxLength = 10;
int step = 1;
int stepCount = 0;

// iteration where the data is added
stepCount = stepCount + 1
if(stepCount >= step) {
    data.push(newData);
    if(data.length > maxLength) {
        for(int i = 1; i < data.length; i++)
            data.splice(i, 1); // removes the value at i
        step = step * 2;
        stepCount = 0;
    }
}

So, basically what it does is I have a step, which is how many iterations I go before putting in new data. It starts at 1.

Every time the array fills up, I remove every odd element (so I never lose my starting value). Then I multiply my step by 2, so it takes twice as long before I add a new value.

Say each iteration I just put a new value counting up, the data would look something like this if maxLength = 4.

1, 2, 3, 4 // step = 1
1, 3 // splice and double step
1, 3, 5, 7 // step = 2
1, 5 // splice and double step
1, 5, 9, 13 // step = 4

And so on. The nice thing is the values are always evenly spaced from each other.

The bad thing is, since step doubles every time it takes longer and longer before new data gets added (when step becomes something like 1024, you have to wait through 1023 iterations). This is where I’d like some improvement, if possible (which it probably isn’t).

The other bad thing is that it can’t run for an infinite amount of time, since eventually step will reach the maximum value for the data type. This can be extended by making step just increase by 1 and then doing 2^step where needed, but it’s still not infinite.

Any help would be great!