Calculating running average in Java

Question

I have a library which makes HTTP calls to my service. I was trying to calculate running average of how much time my service is taking on an average.

Here is the core logic of how I am calculating "running average":

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.LinkedList;
import java.util.Queue;

public class MovingAverage {

    private final Queue<BigDecimal> window = new LinkedList<BigDecimal>();
    private final int period;
    private BigDecimal sum = BigDecimal.ZERO;

    public MovingAverage(int period) {
        this.period = period;
    }

    public void add(BigDecimal num) {
        sum = sum.add(num);
        window.add(num);
        if (window.size() > period) {
            sum = sum.subtract(window.remove());
        }
    }

    public BigDecimal getAverage() {
        if (window.isEmpty()) return BigDecimal.ZERO;
        BigDecimal divisor = BigDecimal.valueOf(window.size());
        return sum.divide(divisor, 2, RoundingMode.HALF_UP);
    }
}

Is there any better/optimized way to do the same thing? I want to make sure this running average calculation is fast since this library runs under very heavy load so this should not increase the overall latency.

Answer 1

Your code looks nice and seems to do exactly what is supposed to be done. I can suggest only one performance related improvement: change LinkedList to ArrayDeque. Don't let the prefix Array scare you: operations add() and remove() are implemented that way that they run in amortized contant time.

I have compared the performance of the both variants (LinkedList versus ArrayDeque):

MovingAverage (with LinkedList) in 1808.1 milliseconds.
MovingAverageV2 (with ArrayDeque) in 1480.6 milliseconds.

Plus, I have a minor comment. Since Java 7, you can write simply

new LinkedList<>();

instead of

new LinkedList<BigDecimal>();

The above syntax sugar is called diamond inference.

Hope that helps.

(PS: If you want to run the performance demonstration, you can find everything needed here.)

Answer 2

I created a ring buffer variant for this answer. It was loosely based upon this question and performs considerably better so it may be beneficial to others; note though that it has not been checked for equivalence (and it uses float instead of BigDecimal):

public class MovingAverage {

    private final float[] window;
    private float sum = 0f;
    private int fill;
    private int position;


    public MovingAverage(int size) {
        this.window=new float[size];
    }

    public void add(float number) {

        if(fill==window.length){
            sum-=window[position];
        }else{
            fill++;
        }

        sum+=number;
        window[position++]=number;

        if(position == window.length){
            position=0;
        }

    }

    public float getAverage() {
        return sum / fill;
    }

}