Design a Moving Average Class for Data Stream

  • 时间:2020-10-07 14:38:56
  • 分类:网络文摘
  • 阅读:80 次

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

1
2
3
4
5
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Compute the Moving Average by using Array or List

The most intuitive method would be to use a vector/array/list to store the numbers. Then we can erase the begining (pop_front) if the size is larger than the window. Then we can go through the window to sum up and compute the moving average.

data-structure-window-queue Design a Moving Average Class for Data Stream algorithms c / c++ data structure math

data-structure-window-queue

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
27
28
29
30
31
32
33
class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        sz = size;
        c = 0;
    }
    
    double next(int val) {
        if (c >= sz) {
            data.erase(data.begin());
            data.push_back(val);
        } else {
            data.push_back(val);
            c ++;
        }
        double r = 0;
        for (int i = 0; i < c; ++ i) {
            r += data[i];
        }
        return r / c;
    }
    
    vector<int> data;
    int sz;
    int c;
};
 
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */
class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        sz = size;
        c = 0;
    }
    
    double next(int val) {
        if (c >= sz) {
            data.erase(data.begin());
            data.push_back(val);
        } else {
            data.push_back(val);
            c ++;
        }
        double r = 0;
        for (int i = 0; i < c; ++ i) {
            r += data[i];
        }
        return r / c;
    }
    
    vector<int> data;
    int sz;
    int c;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

The space complexity is O(W) where W is the size of the moving average window. And the time complexity is also O(W) as we need to iterate W times to compute the sum and thus the moving average.

Using Double-ended Queue to Compute the Moving Average in O(1) constant time

data-structure-deque Design a Moving Average Class for Data Stream algorithms c / c++ data structure math

data-structure-deque

A better way to design the Moving Average class is to use deque (the double-ended queue). We also use a variable to store the sum of the moving average and update it when an element is pop from the begining of the queue and appended into the rear of the queue. Please note that the pop_front and push_back of the deque run at O(1) constant time – which makes the overall time complexity is O(1) and the space requirement is O(W) where we need to store all the numbers in the moving average window.

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
27
28
29
30
class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        M = size;
    }
    
    double next(int val) {
        if (data.size() < M) {
            data.push_back(val);
            sum += val;
            return (double)sum / data.size();
        }
        sum -= data[0];
        data.pop_front();
        sum += val;
        data.push_back(val);
        return (double)sum / data.size();
    }
private:
    deque<int> data;
    int M;
    int sum = 0;
};
 
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */
class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        M = size;
    }
    
    double next(int val) {
        if (data.size() < M) {
            data.push_back(val);
            sum += val;
            return (double)sum / data.size();
        }
        sum -= data[0];
        data.pop_front();
        sum += val;
        data.push_back(val);
        return (double)sum / data.size();
    }
private:
    deque<int> data;
    int M;
    int sum = 0;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
校园烟酒浅谈作文900字  美丽的小院作文  百年世博,梦圆上海  我爱我美丽的家乡作文  辉煌明天  如果把铁块竖放在水中,那么水面上升多少厘米  A×B×C=300,A×C=100,A×4=C  24点题:给定2、6、9、9四个数  数学题:他们到达A、B两地的中点C地时都会提速20%  一个数的近似值是20万,这个数最大是多少?最小是多少? 
评论列表
添加评论