我的基本想法是创建一个链表,然后随着每个新值的出现,将新值加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方向移动。这就是让我怀疑是否需要双向链表的原因。

我将不胜感激任何建议。

最佳答案

我认为最简单的实现是使用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())

关于python - 如何创建时间序列中最后N个项目的运行平均值?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/26204438/

10-11 23:02
查看更多