Program is receiving approximately 50,000 numbers every second.
At ANY given moment, I need to calculate minimum, maximum and average of the values (numbers) that arrived in the last second (regarding to given moment).
Is there a way to do this without using array or list (buffer) to store arriving numbers and to calculate results?
If I need to use buffer, what would be the efficient way to achieve this?
(Note that numbers from buffer also must be efficiently removed from time to time)
Here is an algorithm that will somewhat work to save efficiency in certain cases:
As events come in, buffer them completely, and calculate a running sum, count, min, max (trivial).
When a request for average, min, or max is made, loop through from the back of the buffer and start removing values older than one second. Subtract from sum and count as you go.
If the values are all above min you can keep your min. If the values are below max, you can keep your max. In this scenario, you have average, min, and max updated efficiently.
If the values are below min or above max, you'll need to loop through the rest of the array and recalculate it.
Do step two once a second or so also so that the buffer doesn't get too full. This code could be performed on every buffer insert also, or wherever made sense.
Best structure for this kind of work is a circular buffer, to avoid memory allocations and GC getting in the way. It should be large enough to cover the worst case scenario for message size per second.
Updates
Depending on the usage scenario one other thing to do would be to run the algorithm above but in 10 x 100ms chunks rather than 1 x 1000ms piece. That is, keep the running min, max, sum and count on those 10 chunks. Then when you reach an 'invalidation' scenario, you generally only need to look through the latest 100ms of data or a quick pass through the min and max of the other 9 chunks.
@ja72 provided a great idea to save on finding the min and max values if they are invalidated:
Instead of keeping the min/max values x_min, x_max keep instead the index of where they are located in the x[i] array with i_min and i_max. Then finding them can be trivial sometimes, but when the last value considered holds the min and max, the entire list needs to be scanned to establish the new limits.
Sam Holder had another good idea in the comments - keep a parallel array that is always sorted, this lets you lop numbers off the top or bottom to find new minimums and maximums easier. However, insert speed here is compromised a little (needs to remain in order).
Ultimately, the right choice will depend on the usage characteristics of the program. How often will values be read vs how often they are inserted?
Use circular buffer with each element having timestamp and data, having maximum number of the elements per second as the size of the circular buffer.
As each element is inserted into buffer head, check for the expiration on the other side of the buffer, delete the element.
If the deleted element is minimum or maximum, you'll have to calculate new min/max. If it isn't, you will update min/max according to the new arrivals.
For the avg, keep the total, keep the count, and divide.
can't you keep a queue with your numbers and their arrival times, along with the current maximum & minumum values in the queue (will probably need to keep count of the number of values at the same min/max) and total value of all numbers in the queue and count of elements.
Then when a number arrives add it to the queue and adjust the min/max/value and count. Then look at the other end of the queue and remove all elements that are not within 1 sec of the arrival of the last number, and again adjust the max/min/count/total value.
Then you don't need to keep calculate anything at an instant, just return the precalculated stuff (ie read the current value of min/max or total/count)
As @yaman pointed out you can't retain just the min and max as when one gets removed you might not know the new one. in this case I would probably just keep a second copy of all the numbers in the list but rather than ordered by arrival time I would order by value. Then you just add and remove each number from this list as well, so you'll always know the max and minimum values. This saves you having to scan all elements in the buffer to find the new max/min, at the expense of keeping 2 copies, but updates to this list should be cheap as it is already ordered.
@DanRedux is correct; you will need to calculate them each time because your input is changing. Now, you may prefer to calculate these numbers on demand or up front (i.e., when you get a new batch) depending on how often the results are needed.
For example, if your average use case polls for these stats every ~30 seconds then I would probably just calculate them on demand and cache the result until a new batch comes in. It really comes down to your usage scenario though.
As for how to store them, you don't really have a choice, do you? You need space for all 50,000 numbers in memory. So... you need a chunk of memory large enough to hold them. To avoid constantly allocating 2KB every time a new sequence comes in you're probably better off declaring an array large enough to hold the largest data set possible and just reusing it. Again, this comes down to your requirements, i.e., do you know what your largest possible data set will be? Does allocating a new chunk of memory ever second cause problems in your application over time?
If the average of the last N values x[0] .. x[N-1] is m_1 (x[0] is the latest value, and x[N-1] the last value considered) then the average m_2 of the values pushing everything back by one index and adding the value x is
m_2 = m_1+(x-x[N-1])/N;
for(i=N-1;i>0;i--) { x[i]=x[i-1]; }
x[0] = x;
Instead of keeping the min/max values x_min, x_max keep instead the index of where they are located in the x[i] array with i_min and i_max. Then finding them can be trivial sometimes, but when the last value considered holds the min and max, the entire list needs to be scanned to establish the new limits.
There's an efficient way to keep track of the minimum (or maximum) value within a given time window without usually having to store all the numbers that have arrived within that window. (However, the worst case scenario still does require storing all the numbers, so you need to reserve space for all of them or accept that you may sometimes get incorrect results.)
The trick is to only store values that:
A suitable data structure for implementing this is a simple circular buffer storing values and their arrival times. You'll need to maintain two indices into the buffer. Here's a simple English description of the algorithm:
At startup:
val of values and a corresponding N-element buffer time of timestamps.imax = 0 (or any other value between 0 and N−1 inclusive) and let inext = imax. This indicates that the buffer is currently empty.When a new value new is received at time t:
imax ≠ inext and time[imax] is outside the interval, increment imax by one (modulo N).imax ≠ inext and val[inext-1] ≥ new, decrement inext by one (modulo N).val[inext] = new and time[inext] = t.inext ≠ imax-1, increment inext by one (modulo N); else deal with the "buffer full" condition appropriately (e.g. allocate a larger buffer, throw an exception, or just ignore it and accept that the last value was not correctly recorded).When the minimum value is requested:
imax ≠ inext and time[imax] is outside the interval, increment imax by one (modulo N).imax ≠ inext, return val[imax]; else return an error indicating that no values have been received within the time interval.If the values received are independent and identically distributed (and arrive as a Poisson process), I believe it can be shown that the average number of values stored in the list at any given time is ln(n+1), where n is the average number of values received within the time interval. For n = 50,000, ln(n+1) ≈ 10.82. However, one should keep in mind that this is only the average, and that several times more space may occasionally be required.
For the average, the same trick unfortunately doesn't work. If possible, you could switch to an exponentially moving average, which can be easily tracked using very little space (just one number for the average and one timestamp indicating when it was last updated).
If that's not possible, but you're willing to accept a small amount of smoothing in the average values, you could calculate an average over, say, each millisecond. That way, whenever an average of the values over the last second is requested, you can just take an average of the last 1001 millisecond averages, weighing the oldest and newest of them according to how much of those milliseconds lie within the interval:
At startup:
sum of values and an n+1 -element buffer cnt of non-negative integers, and fill both with zeros.prev have any value. (It doesn't really matter.)When a new value new is received at time t:
i = floor(t / dt) mod (n+1).i ≠ prev:
sum[i] from total and cnt[i] from count.sum[i] = 0, cnt[i]= 0 and let prev = i.new to sum[i] and increment cnt[i] by one.new to total and increment count by one.When the average value is requested at time t:
i = floor(t / dt) mod (n+1).i ≠ prev:
sum[i] from total and cnt[i] from count.sum[i] = 0, cnt[i]= 0, and let prev = i.j = (i−n) mod (n+1) = (i+1) mod (n+1).w = frac(t / dt) = (t / dt) − floor(t / dt).total − w × sum[j]) / (count − w × cnt[j]).
Sadly, there isn't. The reason why it's not possible is because you need to only account for them that are a second old, which means you have to re-calculate the result every time, which means HUGE loops.
If you wanted to calculate the last 40,000 numbers, or all of them, it would be easier, but because it's time-based, you have to loop through the entire list every time.
Is there a way to do this without using array or list (buffer) to store arriving numbers and to calculate results?
No. It's provably impossible to do this without storing the information, as you stated it. You could tweak the requirements a bit to get rid of the need for a buffer though.
If I need to use buffer, what would be the efficient way to achieve this?
You'll want to use a Queue for this.
When an item is added, if it's the new max or min adjust those variables accordingly. You can incrementally adjust the mean through the formula here. Just Take the new value, minus the mean, divided by the new number of items in the set (i.e. size of queue plus one) and then add that to the old mean.
Then you'll have something more or less like this:
while(queue.Peek < oneSecondAgo)
{
oldItem = queue.Peek
queue.Dequeue();
if(oldItem == min) //recalculate min
if(oldItem == max) //recalculate max
mean += SubtractValueFromMean(oldItem.Value, queue.Count);
}
To remove the value from the mean you should be able to just use the same formula for adding, but use the negative of the value rather than the positive...I think. A better mathematician may need to help you out here.
If the numbers are coming one after the other, then use a stopwatch and a while loop to get every number one by one for one second, and calculate min, max, and avg.
double min = double.MaxValue;
double max = double.MinValue;
double sum = 0;
int count = 0;
double avg;
StopWatch sw = new StopWatch();
sw.Start();
while(sw.Elapsed.TotalSeconds <= 1)
{
// Get the next number in the stream of numbers
double d = GetNextNumber();
// Calculate min
if(d < min) min = d;
// Calculate max
if(d > max) max = d;
// Calculate avg = sum/ count
sum += d;
count++;
}
avg = sum/count;
Then return min, max, and avg.
It's not possible to do without holding on to the numbers in a buffer or queue.
The reason for that is simple: when a maximum value expires (falls out of the 1 second window), the new maximum is some other number that arrived within the last second, so you need to have a record of the candidates that could become the new maximum.
Needing the average means all values have an effect when they expire, and nothing can be thrown out before it's one second old.
Sam Holder's suggestion of using a queue is a good one, though you'll likely need a specialized one that can keep your list in two orders simultaneously: the order in which the numbers were received (arrival time), and ordered from maximum to minimum.
Using a single node object with two next and two previous pointers (one pair temporally, and the other in terms of size) would make it possible to remove elements from both lists simultaneously, when an element expires from the temporal list, you have access to the pointers for the size list, because they're in the same node object.
The average can be maintained by keeping a running total and a running count, subtracting elements as they are removed, and adding them as they are created, so it is not necessary to iterate over the whole list each time in order to calculate the average.
As btilly suggested in their comment on Sam Holder's post, it would be more efficient to use a max heap and a min heap than to use a list, we would again need to use a single node with pointers for both heaps and the list, so we don't have to search for elements to remove them, and it might be necessary to spend some time considering how to properly remove elements not at the top of the heap, while maintaining the guarantee of O(log n) insertions and removals.
For average, there are 3 cases to consider:
For min and max (only relevant for #1 and #3 above):
As you add and remove values to and from the linked list, perform corresponding operations on the treap. To get a min and max from the treap, just do find_minimum and find_maximum operations in log(n) time. As you remove things from the right end of the linked list in constant time, also remove them from the treap in log(n) time.
Treaps can find their minimum value in log(n) time, find their maximum value in log(n) time, and find an arbitrary value in log(n) time. In general, the more different ways you need to access your data, the better a well-rounded datastructure like a treap looks.
