Moving Average from Data Stream

class RunningAverage {
  int capacity, index = 0, sum = 0, elements = 0;
  int[] data;
  public RunningAverage(int capacity) {
    this.capacity = capacity;
    data = new int[capacity];
  }

  public double next(int value) {
    ++elements;
    int last = (index + 1) % capacity;
    sum = sum - data[last] + value;
    index = (index + 1) % capacity;
    data[index] = value;
    return sum * 1.0 / Math.min(capacity, elements);
  }
}

The "Moving Average from Data Stream" code implementation in Java provides a robust way to calculate the running average of the last n values from a stream of integers using a circular array mechanism for efficient memory utilization.

• Initialize and prepare a data structure using a fixed-sized array, where the size is defined by the capacity, given during the creation of a RunningAverage object.
• The next method handles the inclusion of the next number from the stream into the moving average calculation:
  • It increments the count of the total elements received.
  • Calculates the new index for the insertion of the incoming value by using modulo operation, which helps in making the array work as a circular data structure.
  • Updates the sum by subtracting the value that will be overwritten and adding the new value.
  • Stores the new value in the calculated position in the array.
  • Computes the current average by dividing the current sum by the smaller of the number of elements received or the capacity.

This approach ensures that once the capacity of the data structure is filled, new entries overwrite the oldest entries, thus maintaining a sliding window of the last n entries for the average computation. This method is very efficient concerning time and space complexities, ensuring the program runs in constant time O(1) with space also being constant, O(n), relative to the capacity of the moving average calculation window.

class AverageCalculator:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items = [0] * self.capacity
        self.first = self.total_sum = 0
        self.elements = 0

    def next_value(self, num: int) -> float:
        self.elements += 1
        # Advance the end of the window
        end = (self.first + 1) % self.capacity
        self.total_sum = self.total_sum - self.items[end] + num
        # Update the new start position
        self.first = (self.first + 1) % self.capacity
        self.items[self.first] = num
        return self.total_sum / min(self.capacity, self.elements)

This solution implements a class AverageCalculator in Python to determine a moving average from a stream of data, using a sliding window approach.

• The class is initialized with a capacity which determines the size of the moving window.
• Inside the class:
  • self.items stores the current values within the window.
  • self.first tracks the starting index of the sliding window.
  • self.total_sum accumulates the sum of the values in the current window.
  • self.elements counts the total number of values processed, which is useful for handling cases when fewer than capacity elements have been added.

The method next_value(num: int) -> float updates the moving average each time a new value enters:

1. Increment self.elements by 1 to acknowledge the new entry.
2. Calculate end, the next index in the circular list structure, by (self.first + 1) % self.capacity.
3. Adjust self.total_sum by subtracting the value that exits the window (self.items[end]) and adding the new value (num).
4. Update self.first for the next round using a circular increment.
5. Replace the oldest number in self.items with num.
6. Return the current average, calculated by dividing self.total_sum by min(self.capacity, self.elements), ensuring a correct average during the initial fill-up phase.

This structure allows the AverageCalculator to efficiently compute the moving average with constant time complexity per insertion, suitable for high-volume data streams where efficiency is critical.