Moving Average of Last N numbers in a Stream

Moving Average of Last N numbers in a Stream - Algorithms and Problem SolvingAlgorithms and Problem Solving

Design a class to calculate moving average of last N numbers in a stream of real numbers

Moving Average of All numbers in a stream

This is pure math. If we have seen total n numbers so far and current average is avg then when we add a new element the new average would be avg=(n*avg+new_element)/(n+1). Below is a pseudocode to find moving average of all numbers in a stream in O(1) time –

avg = 0;
n = 0;

def add(element):
  avg = (n*avg)/(n+1);
  n++;
end

def getAvg()
  return avg;
end

Moving Average of Last N Numbers

Queue queue;
double avg;

def add(num) :
    double
    if(queue.size() == N) then
         avg = (N*avg-queue.dequeue()+num)/N
    else
         avg = (queue.size()*avg+num)/(queue.size()+1)
         queue.add(num);
    end
end

Can we do better without any special data structure?

public static class MovingAvgLastN{
 int maxTotal;
 int total;
 double lastN[];
 double avg;
 int head;
 
 public MovingAvgLastN(int N){
  maxTotal = N;
  lastN = new double[N];
  avg = 0;
  head = 0;
  total = 0;
 }
 
 public void add(double num){
  double prevSum = total*avg;
  
  if(total == maxTotal){
   prevSum-=lastN[head];
   total--;
  }
  
  head = (head+1)%maxTotal;
  int emptyPos = (maxTotal+head-1)%maxTotal;
  lastN[emptyPos] = num;
  
  double newSum = prevSum+num;
  total++;
  avg = newSum/total;
 }
 
 public double getAvg(){
  return avg;
 }
}

Use LinkedList as queue or circular array(is better, as it can reuse space, less space(no pinter)).
http://rosettacode.org/wiki/Averages/Simple_moving_average#Java

public class MovingAverage {
    private final Queue<Double> window = new LinkedList<Double>();
    private final int period;
    private double sum;
 
    public MovingAverage(int period) {
        assert period > 0 : "Period must be a positive integer";
        this.period = period;
    }
 
    public void newNum(double num) {
        sum += num;
        window.add(num);
        if (window.size() > period) {
            sum -= window.remove();
        }
    }
 
    public double getAvg() {
        if (window.isEmpty()) return 0; // technically the average is undefined
        return sum / window.size();
    }
}

get average on sliding window, how to do it thread safe without lock
他让我把update value那几个地方改成CAS。
Read full article from Moving Average of Last N numbers in a Stream - Algorithms and Problem SolvingAlgorithms and Problem Solving