Running Average

The running average, or moving average, at a point in a sequence is the average of the previous n elements up to that point. It provides a smoothed value as it progresses through the sequence.

The formula for the running average of the previous n elements is:

avg(i) = (x(i) + x(i-1) + … + x(i-n+1)) / n

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

double[] runningAvg(int[] arr, int n) {
  double[] avg = new double[arr.length];
  double sum = 0;

  for (int i = 0; i < n; i++) {
    sum += arr[i];
  }

  avg[n-1] = sum / n; 
  for (int i = n; i < arr.length; i++) {
    sum += (arr[i] - arr[i-n]);
    avg[i] = sum / n;
  }

  return avg;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

vector<double> runningAvg(vector<int> arr, int n) {
  vector<double> avg(arr.size());
  double sum = 0;

  for (int i = 0; i < n; i++) {
    sum += arr[i];
  }

  avg[n-1] = sum / n;
  for (int i = n; i < arr.size(); i++) {
    sum += (arr[i] - arr[i-n]);
    avg[i] = sum / n;
  }

  return avg;
} 

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def running_avg(arr, n):

  avg = [0] * len(arr)
  sum = 0

  for i in range(n):
    sum += arr[i]
  avg[n-1] = sum / n

  for i in range(n, len(arr)):
    sum += arr[i] - arr[i-n]
    avg[i] = sum / n

  return avg

The running average smooths out variances to identify trends. Useful for time series smoothing.

Running average, also known as moving or rolling average, refers to a calculation that continually updates the average of a series of numbers as new numbers are added. It is commonly used in time-series data to smooth out short-term fluctuations and highlight long-term trends or cycles.

Here’s how it works:

1. Determine the window size (e.g., the last N numbers you want to average).
2. As a new number is added to the series, include it in the average and exclude the number that falls out of the window (if the window is full).
3. Update the average to reflect the current numbers in the window.

The running average can be calculated using a fixed window (e.g., the average of the last 5 numbers) or an expanding window (e.g., the average of all numbers up to the current one).

Example

Let’s consider calculating the running average for the following series with a window size of 3: [5, 10, 15, 20, 25].

• For the first number (5), the average is 5.
• For the first two numbers (5, 10), the average is 7.5.
• For the first three numbers (5, 10, 15), the average is 10.
• For the next three numbers (10, 15, 20), the average is 15.
• For the last three numbers (15, 20, 25), the average is 20.

The running averages are [5, 7.5, 10, 15, 20].

Running averages are often used in finance, economics, and engineering to analyze trends and patterns. It’s a simple yet powerful tool for data analysis, as it helps in visualizing and understanding underlying trends in the data.

Description

The concept of Running Average, or moving average, is essential in many fields such as finance, physics, and statistics. It involves calculating the average of a set of numbers as you progress through a data set. With each new data point, the oldest data point is dropped, and the newest one is added to the calculation. This continuous update of the average helps in smoothing the data, revealing underlying trends, and is particularly useful in reducing random noise.

Solution

Java

In Java, you can calculate the Running Average by iterating through the array and updating the sum by adding the new element and subtracting the oldest one.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class RunningAverage {
    private int size;
    private double total = 0d;
    private int elementCount = 0;
    private int[] elements;

    public RunningAverage(int size) {
        this.size = size;
        elements = new int[size];
    }

    public void add(int value) {
        if (elementCount < size) {
            elementCount += 1;
        } else {
            total -= elements[elementCount % size];
        }

        total += value;
        elements[elementCount % size] = value;
    }

    public double getAverage() {
        return total / elementCount;
    }
}

C++

In C++, you can implement the running average by using a queue and updating the sum as elements are added and removed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <queue>

class RunningAverage {
private:
    std::queue<int> elements;
    double sum = 0;
    int size;

public:
    RunningAverage(int size) : size(size) {}

    void add(int value) {
        if (elements.size() == size) {
            sum -= elements.front();
            elements.pop();
        }
        
        sum += value;
        elements.push(value);
    }

    double getAverage() {
        return sum / elements.size();
    }
};

Python

In Python, you can utilize a deque with a maxlen attribute to automatically remove the oldest element when the size is reached.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from collections import deque

class RunningAverage:
    def __init__(self, size):
        self.size = size
        self.elements = deque(maxlen=size)
        self.total = 0

    def add(self, value):
        if len(self.elements) == self.size:
            self.total -= self.elements[0]
        
        self.elements.append(value)
        self.total += value

    def getAverage(self):
        return self.total / len(self.elements)

The examples in Java, C++, and Python show how you can maintain a running average as new elements are added to the data set. By keeping track of the sum and managing the removal of the oldest element, the running average can be computed efficiently.

Tabular Representation

Below is a table that illustrates how the running average is calculated with each new element in the array. Let’s say we have a window size of 3 for our running average, and we’ll use the input array [4, 2, 8, 5, 10].

Explanation:

• Iteration 1: The first element is 4, so the running sum is 4, and the average is 4.
• Iteration 2: The second element is 2, so the running sum is 4 + 2 = 6, and the average is 3.
• Iteration 3: The third element is 8, so the running sum is 4 + 2 + 8 = 14, and the average is 4.6667.
• Iteration 4: The fourth element is 5. Since the window size is 3, the oldest element (4) is dropped. So, the running sum is 2 + 8 + 5 = 11, and the average is 3.6667.
• Iteration 5: The fifth element is 10. Since the window size is 3, the oldest element (2) is dropped. So, the running sum is 8 + 5 + 10 = 23, and the average is 7.6667.

The running average calculation continues in this manner, with each new element updating the sum and the oldest element being dropped when the window size is reached.

Below is a visual representation that illustrates how the window moves through the array for the running average with a window size of 3, using the same input array [4, 2, 8, 5, 10].

Explanation:

• In the first row, the brackets [...] surround the current window, which includes only the first element (4) at this point.
• In the second row, the window has moved to include the first two elements (4 and 2).
• In the third row, the window now includes the first three elements (4, 2, and 8), and the running average is calculated over these three numbers.
• In the fourth row, the window moves one step to the right, dropping the first element and including the next (2, 8, 5).
• In the fifth row, the window moves again, now including the last three elements (8, 5, 10).

As the window moves through the array, the running average is recalculated at each step, always considering the numbers within the current window.