java - 算法——求循环缓冲区中数字的平均值？

Question

我正在尝试考虑一种算法来跟踪循环缓冲区中数字的平均值，假设数字在缓冲区接近容量时被覆盖。

e.g. size = 4 
[1,2,7,3] => avg = 13/4 = 3.25
add(5)
[5,2,7,3] => avg = 17/4 = 4.25

这是我目前的做法。

class CircularBuffer {

    int[] buffer;  
    int head;
    int tail;
    int sum;

    public CircularBuffer(int n) {   
        tail = 0;
        head = 0;
        buffer = new int[n];
    }

    void addNumber(int number) {  
        if (head == tail - 1) {
            sum -= buffer[tail - 1];
        } else if (head != tail - 1) {
            buffer[head++]= number;
            sum += number;
        }

        head = head % buffer.length;                 
    }

    double avg() {        
        if (head > vtail) {
            return sum / (head - tail + 1);
        } else { 
            return sum / buffer.length;
        }
    }

    public static void main(String[] args) {
        CircularBuffer buf = new CircularBuffer(3);
        buf.addNumber(1);
        buf.addNumber(2);
        buf.addNumber(3);
        buf.addNumber(4);
        System.out.println("Avg"+ buf.avg());                     
    }

什么不起作用:目前返回 5 而不是 3。

Answer 1

你真的不需要尾部，你只需要知道你是否达到了缓冲区的长度，所以代码看起来像这样:

class CircularBuffer {

    int tail = 0;
    int head = 0;
    int[] buffer;
    int sum = 0;

    public CircularBuffer(int n) {
        buffer = new int[n];
    }

    void addNumber(int number) {
        sum -= buffer[head];
        sum += number;
        buffer[head++] = number;
        head = head % buffer.length;
        if (tail <= buffer.length) {
            tail++;
        }
    }

    double avg() {
        if (head == tail) {
            return (double) sum / (double) head;
        } else {
            return (double) sum / (double) buffer.length;
        }
    }

    public static void main(String[] args) {

        CircularBuffer buf = new CircularBuffer(3);
        buf.addNumber(1);
        buf.addNumber(2);
        buf.addNumber(3);
        buf.addNumber(4);
        System.out.println("Avg" + buf.avg());
    }
}

由于 buffer = new int[n]; 用零填充缓冲区，您不需要在方法 addnumber 中使用任何 if/else，您只需减去前一个值并添加当前值。希望一切都清楚。