Formula to calculate average number on expanding data array

Question

Say, if I had a final array of numbers, say:

{1, 5, 7, 2}

the average for them will be:

(1 + 5 + 7 + 2) / 4;   //Or, sum of all elements, divided by their number

But what if my array is constantly growing and I need to know the current average number at an instance of time when the full array is not known yet. How do you calculate that?

Say, like when I'm trying to display current data transfer rate.

Answer 1

I would go with a simple approach for having a running total (cumulative) with a constant space complexity (1). And on request of avg, return the result which is running total/total number of item. No extended time complexity since we don't iterate array afterwards to find cumulative sum.

Answer 2

Every time you get a new value update your sum and count and simply divide the two when you need to display them to the user.

For data transfer rate this is problematic approach though. Think of the scenario where you start a transfer with high bandwidth and then the connection drops, with a simple average it could take a long time for your UI to reflect that the current transfer rate is 0. Using a weighted moving average is a quick way to make your UI seem more responsive.

The simplest implementation of this is to sample the transfer rate periodically (say every 5 seconds) and calculate your rate with something like:

 float weight = 2.0; //you are going to want to tweak this to get the right balance between "responsive" and "noisy"

 void UpdateAverage(float newValue)
 {
    this.Average = (this.Average + (newValue*weight))/(weight+1)
 }

Answer 3

I know I'm late to the party here but I solved a similar problem to this back in 2000, when I was creating an adaptive load balancer. The standard average has two problems, both mentioned in the answers given:

1. The overflow scenario
- Keeping a running total will lead to overflow
2. Recalculating average
- Ordinarily, you have to do this for every single sample

So you can turn the normal average calculation into a what maths folk call a 'recurrence relation' which means you store the previous average, which is then used to calculate the new one (akin to Yaur's answer, which I have to agree with ahmed, I can't see it was down-voted). I wrote the original in Delphi back in the day, so I very recently did the same thing again in .NET and compared it against the standard process of calculating continual averages as lists of items get bigger.

Without wanting to self-promote (I'm posting the link just to save my typing fingers), you can find the theoretical treatment, algebra, results of the comparison experiments and how it addresses the problems at:

http://goadingtheitgeek.blogspot.co.uk/2014/05/blast-from-past.html

I hope you find it useful.

Answer 4

You're looking for a moving average:

    static void Main(string[] args) {
        var nums = Enumerable.Range(1, 5).Select(n => (double)n);
        nums = nums.Concat(nums.Reverse());

        var sma3 = SMA(3);
        var sma5 = SMA(5);

        foreach (var n in nums) {
            Console.WriteLine("{0}    (sma3) {1,-16} (sma5) {2,-16}", n, sma3(n), sma5(n));
        }
    }

    static Func<double, double> SMA(int p) {
        Queue<double> s = new Queue<double>(p);
        return (x) => {
            if (s.Count >= p) {
                s.Dequeue();
            }
            s.Enqueue(x);
            return s.Average();
        };
    }

Source: http://rosettacode.org/wiki/Averages/Simple_moving_average#C.23

Answer 5

My bet is that you want something fast, otherwise you already have your answer. Sum all numbers that you already have by the length of the array you already have. This is very straightforward.

However sometimes you cannot know if the array will be bounded, it can be infinite, such as the data coming from a microphone. The suggestion of the moving average is good in this case, it means that you have to take the last x values from the array and calculate the average on those values only. The algorithm and the time required to compute the result stays the same whether you have x values or 1000x values.

edit :

the x vs 1000x comes from algo complexity. Suppose that you sum 5 numbers, that is 5 operations, then you divide by 5, another operation for a total of 6 ( for the sake of the example we'll assume that they all take the same computer time but in reality dividing is slow compared to adding ). If you take the same code but with 1000 numbers, you do 1001 operations which is going to take much more time than in the first case!

With the "moving average", you always take a fixed number of numbers so your algo takes a fixed amount of time to execute no matter if you have 5 or 1000 numbers.

Moving average is just a fancy wording to say that you do not take the same numbers in your array from one time to another. Imagine the following array :

int x = { 1, 4, 6, 3, 1 };
int arrayLength = 5;

Then the average of this array will be

int runningTotal = 0;
for(int i = 0; i < arrayLength; i++)
{
   runningTotal += x[i];
}
double average = runningTotal / arrayLength

The moving average of 3 values would be

int movingLength = 3;
int runningTotal = 0;
for(int i = 0; i < movingLength; i++)
{
   runningTotal += x[arrayLength - i - 1];
}
double average = runningTotal / movingLength;

So the first values in the array are not part of the calculation when the array grows.

Answer 6

Assuming you don't want a moving average..

You need to keep track of the current sum of the elements when you last calculated the average.

If your array is this...

Array = {1, 5, 7, 2}
Sum = 1 + 5 + 7 + 2 = 15
Number of elements = 4
Average = Sum / Number of elements = 3.75

You add a couple of elements and your array looks like this...

Array = {1, 5, 7, 2, 10, 6}

Assuming your actual array is much larger... To recalculate your average..

Sum = ([previous sum] + [sum of new elements]) / [number of elements]
Number of elements = 6
Average = ((15 * 4) + 10 + 6) / 6 = 5.1666667

Edit: if you are concerned about precision and size check out the BigInteger

Answer 7

if average buffer length is changable my old program is that.

namespace WindowsFormsApplication1
{
  public partial class ComTester : Form
  {
    public int []sAvgArr=new int [251];
    public int sAvgAdr,sAvgCnt;

    private void Calc_Values(object sender, int v)//v is value
    {
        int n = AverageLength;
        if (n > 250) n = 250;//average buffer maksimum
        if (n > 0)
        {
            sAvgArr[sAvgAdr] = v;
            sAvgAdr += 1;
            sAvgCnt += 1;
            if (n <= sAvgAdr) sAvgAdr = 0;
            if (n <= sAvgCnt) sAvgCnt = n;
            n = sAvgCnt;
            int f = 0, l = 0; ;
            for (l = 0; l < n; l += 1)
                f += sAvgArr[l];
            f = f / sAvgCnt;
            sAvgVal = f;
        }
        else 
        {
            sAvgVal=v;
        }
    }
  }
}

Answer 8

using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int  n = 3 , x , sum = 0 ;
            double ave;

            for (int i = 0; i < n; i++ )
            {
                Console.WriteLine("enter the number:");
                x = Convert.ToInt16(Console.ReadLine());
                sum += x;
            }

            ave = (double)(sum) / 3;
            Console.WriteLine("average:");
            Console.WriteLine( ave );
            Console.ReadLine();
        }
    }
}