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) —

推荐阅读:
How to Flip Equivalent Binary Trees?  How to Implement Quicksort Algorithm in Python – the Pytho  How to Compute the Clumsy Factorials using Iterative Algorithm?  How to Convert Float Number (Fraction) to Hexadecimal in Python?  4 Tips You Shouldn’t Miss While Creating Your Ideal Websit  SQL Algorithm to Compute Shortest Distance in a Plane  How to Count Univalue Subtrees in a Binary Tree?  Have Writer’s Block? Try These Content Ideation Tools for Market  Quick Ways to Relax Once You’ve Hit Publish  How to Prepare Your SEO Strategy for the Internet of Things 
评论列表
添加评论