如何創建時間序列中最後N個項目的運行平均值？

Question

我的基本想法是創建一個鏈表，並且隨着每個新值進來，添加新值的1/N並減去第一個值的1/N，然後將指針先移動一個，然後釋放與第一個關聯的內存。

這不會最終在Python中實現，但只是爲了讓我的頭腦清楚這個過程，我試圖用Python編寫它，但是我的實現是有缺陷的。我需要一個雙向鏈表嗎？是否有替代方法（不是基於鏈表）更好？

這裏是我的嘗試至今：

class Link: 
    def __init__(self,val): 
     self.next = None 
     self.value = val 

class LinkedList: 
    def __init__(self,maxlength): 
     self.current_link = None 
     self.maxlength = maxlength 
     self.sum = 0. 
     self.average = None 
     self.length = 0 
     self._first_link = None 
    def add_link(self,val): 
     new_link = Link(val) 
     new_link.next = self.current_link 
     self.current_link = new_link 
     if self._first_link is None: 
      self._first_link = self.current_link 
     self.sum += val 
     if self.length < self.maxlength: 
      self.length += 1 
     else: 
      self.sum -= self._first_link.value 
      self._first_link = self._first_link.next # this line is flawed 
     self.average = self.sum/self.length 
    def get_first(self): 
     return self._first_link.value 

# Main 
ll = LinkedList(5) 
for ii in xrange(10): 
    ll.add_link(ii) 
    print ii,ll.get_first(),ll.average 

的問題是，_first_link被設置爲不明確下一個值。也就是說，_first_link被設置爲添加的第一個項目，但其下一個是None，所以我不知道如何按照我的意願將它移動1。這是什麼讓我想知道是否需要一個雙向鏈表。

我會很感激任何建議。

Answer 1

我認爲最簡單的實現是使用circular linked list（又名一個環）：

class Link(object): 
    def __init__(self, value=0.0): 
     self.next = None 
     self.value = value 

class LinkedRing(object): 
    def __init__(self, length): 
     self.sum = 0.0 
     self.length = length 
     self.current = Link() 

     # Initialize all the nodes: 
     last = self.current 
     for i in xrange(length-1): # one link is already created 
      last.next = Link() 
      last = last.next 
     last.next = self.current # close the ring 

    def add_val(self, val): 
     self.sum -= current.value 
     self.sum += val 
     self.current.value = val 
     self.current = self.current.next 

    def average(self): 
     return self.sum/self.length 


# Test example: 
rolling_sum = LinkedRing(5) 
while True: 
    x = float(raw_input()) 
    rolling_sum.add_val(x) 
    print(">> Average: %f" % rolling_sum.average()) 

Answer 2

好的，我想到了一個在O [1]時間內工作的解決方案。我仍然好奇，如果任何人有一個鏈表爲主的解決方案，但這種解決方案避免了完全LL：

class Recent: 
    def __init__(self,maxlength): 
     self.maxlength = maxlength 
     self.length = 0 
     self.values = [0 for ii in xrange(maxlength)] 
     self.index = 0 
     self.total = 0. 
     self.average = 0. 
    def add_val(self,val): 
     last = self.values[self.index%self.maxlength] 
     self.values[self.index%self.maxlength] = val 
     self.total += val 
     self.total -= last 
     if self.length < self.maxlength: 
      self.length += 1 
     self.average = self.total/self.length 
     self.index += 1 
    def print_vals(self): 
     print "" 
     for ii in xrange(self.length): 
      print ii,self.values[ii%self.maxlength] 
     print "average:",self.average 

# Example to show it works 
rr = Recent(5) 
for ii in xrange(3): 
    rr.add_val(ii) 
rr.print_vals() 
for ii in xrange(13): 
    rr.add_val(ii) 
rr.print_vals() 

Answer 3

您可以實現這一點使用collections.deque和維護運行的平均數值穩定數學：

import collections 

class AveragingBuffer(object): 
    def __init__(self, maxlen): 
     assert(maxlen>1) 
     self.q=collections.deque(maxlen=maxlen) 
     self.xbar=0.0 
    def append(self, x): 
     if len(self.q)==self.q.maxlen: 
      # remove first item, update running average 
      d=self.q.popleft() 
      self.xbar=self.xbar+(self.xbar-d)/float(len(self.q)) 
     # append new item, update running average 
     self.q.append(x) 
     self.xbar=self.xbar+(x-self.xbar)/float(len(self.q)) 


if __name__=="__main__": 
    import scipy 
    ab=AveragingBuffer(10) 
    for i in xrange(32): 
     ab.append(scipy.rand()) 
     print ab.xbar, scipy.average(ab.q), len(ab.q)