moving_average_from_data_stream
1from math import isclose 2from collections import deque 3 4# @leet start 5class MovingAverage: 6 """ 7 This class exists to calculate the moving average of a data stream. 8 The constructor receives the size of the window, and the next function 9 is called with a new value to insert and returns the current average of the window. 10 11 One naive approach is to keep an array, and consistently append to it. 12 You can then calculate the average by taking the sum of arr[len - size..] / size. 13 This works, but the amount of space required is $O(n)$ with regard to calls to next. 14 As well, there's a lot of redundancy -- you recalculate the sum of items even though 15 all but one of them has changed, making the average calculation slow for larger values of $size$. 16 17 To deal with both of these, we want to use a data structure that allows us to keep 18 $size$ items, and also allow for easy removal from the beginning and easy appends. 19 This is a queue data structure. 20 21 To make the average calculation easier, we keep the running total of the queue alongside it. 22 So, if the queue has more space, we simply add $val$ to the queue and to our running total. 23 If the queue has no more space, we remove a value from the beginning of the queue, 24 subtract its value from the running total (since it has been removed) and then add our value 25 to both the queue and the running total. We then divide the total by the len to get the average. 26 27 This means that average calculation is now $O(1)$ time, the queue takes $O(size)$ memory, and 28 adding/removing from the queue also takes $O(1)$ time, which is optimal. 29 """ 30 def __init__(self, size: int): 31 self.size = size 32 """The max allowed length of the queue""" 33 self.items = deque() 34 """The queue itself""" 35 self.curr_total = 0 36 """The current sum of the queue""" 37 self.len = 0 38 """The current length of the queue""" 39 40 def next(self, val: int) -> float: 41 if self.len < self.size: 42 self.curr_total += val 43 self.len += 1 44 self.items.append(val) 45 return self.curr_total / self.len 46 else: 47 evicted = self.items.popleft() 48 self.curr_total += (val - evicted) 49 self.items.append(val) 50 return self.curr_total / self.len 51# @leet end 52def test(): 53 sol = MovingAverage(3) 54 assert(sol.next(1) == 1) 55 assert(sol.next(10) == 5.5) 56 assert(isclose(sol.next(3), 4.66667, rel_tol=1e-03)) 57 assert(sol.next(5) == 6.0)
6class MovingAverage: 7 """ 8 This class exists to calculate the moving average of a data stream. 9 The constructor receives the size of the window, and the next function 10 is called with a new value to insert and returns the current average of the window. 11 12 One naive approach is to keep an array, and consistently append to it. 13 You can then calculate the average by taking the sum of arr[len - size..] / size. 14 This works, but the amount of space required is $O(n)$ with regard to calls to next. 15 As well, there's a lot of redundancy -- you recalculate the sum of items even though 16 all but one of them has changed, making the average calculation slow for larger values of $size$. 17 18 To deal with both of these, we want to use a data structure that allows us to keep 19 $size$ items, and also allow for easy removal from the beginning and easy appends. 20 This is a queue data structure. 21 22 To make the average calculation easier, we keep the running total of the queue alongside it. 23 So, if the queue has more space, we simply add $val$ to the queue and to our running total. 24 If the queue has no more space, we remove a value from the beginning of the queue, 25 subtract its value from the running total (since it has been removed) and then add our value 26 to both the queue and the running total. We then divide the total by the len to get the average. 27 28 This means that average calculation is now $O(1)$ time, the queue takes $O(size)$ memory, and 29 adding/removing from the queue also takes $O(1)$ time, which is optimal. 30 """ 31 def __init__(self, size: int): 32 self.size = size 33 """The max allowed length of the queue""" 34 self.items = deque() 35 """The queue itself""" 36 self.curr_total = 0 37 """The current sum of the queue""" 38 self.len = 0 39 """The current length of the queue""" 40 41 def next(self, val: int) -> float: 42 if self.len < self.size: 43 self.curr_total += val 44 self.len += 1 45 self.items.append(val) 46 return self.curr_total / self.len 47 else: 48 evicted = self.items.popleft() 49 self.curr_total += (val - evicted) 50 self.items.append(val) 51 return self.curr_total / self.len
This class exists to calculate the moving average of a data stream. The constructor receives the size of the window, and the next function is called with a new value to insert and returns the current average of the window.
One naive approach is to keep an array, and consistently append to it. You can then calculate the average by taking the sum of arr[len - size..] / size. This works, but the amount of space required is $O(n)$ with regard to calls to next. As well, there's a lot of redundancy -- you recalculate the sum of items even though all but one of them has changed, making the average calculation slow for larger values of $size$.
To deal with both of these, we want to use a data structure that allows us to keep $size$ items, and also allow for easy removal from the beginning and easy appends. This is a queue data structure.
To make the average calculation easier, we keep the running total of the queue alongside it. So, if the queue has more space, we simply add $val$ to the queue and to our running total. If the queue has no more space, we remove a value from the beginning of the queue, subtract its value from the running total (since it has been removed) and then add our value to both the queue and the running total. We then divide the total by the len to get the average.
This means that average calculation is now $O(1)$ time, the queue takes $O(size)$ memory, and adding/removing from the queue also takes $O(1)$ time, which is optimal.
41 def next(self, val: int) -> float: 42 if self.len < self.size: 43 self.curr_total += val 44 self.len += 1 45 self.items.append(val) 46 return self.curr_total / self.len 47 else: 48 evicted = self.items.popleft() 49 self.curr_total += (val - evicted) 50 self.items.append(val) 51 return self.curr_total / self.len