时间戳

首页 > 解决方案 > 在大小 > n 的移动窗口中跟踪前 n 个值？

python - 在大小 > n 的移动窗口中跟踪前 n 个值？

问题描述

假设我们有一个每分钟输入一次的数据流，并且我们希望在前 10 分钟内跟踪前 5 个值。直觉上应该有一些队列解决方案，但我正在努力寻找一种优雅的方式，因为一个元素可以出于两种不同的原因弹出（它看起来在 11 分钟前或 <10 分钟前，但 5 个更高的值有从那以后就被看到了）

任何建议，将不胜感激！

标签： pythonstackqueue

解决方案

不要在这里忽略一个简单的事情——你可能会惊讶于它的效果。您有两个订单，因此请按排序顺序维护两个序列，按bytime时间排序和byvalue按价值排序。在每个中存储 2 元组(value, timestamp)对。当然，您需要使它们保持同步。

由于byvalue始终按值排序，因此您可以随时查看 top n、 bottom n、 middlen或任何其他类型的顺序统计信息。

假设您的时间戳（无论对您意味着什么）只会随着时间的推移而增加，那么按时间“排序”是微不足道的：使用 acollections.deque并在一端（例如右侧）推送新记录并从另一端丢弃。对 .使用普通列表byvalue。要使旧记录过期，则：

oldest_to_retain = whatever form of timestamp you use
while bytime and bytime[0][1] < oldest_to_retain:
    t = bytime.popleft() # discard expired record
    # and remove it from the other seq too
    i = bisect.bisect_left(byvalue, t)
    assert byvalue[i] == t
    del byvalue[i]

要插入传入值，

t = (the_new_value, current_timestamp)
assert not bytime or bytime[-1][1] <= current_timestamp
bytime.append(t)
bisect.insort(byvalue, t)

现在有了一些经验，人们对这个想法犹豫不决，因为这些陈述具有O()线性行为len(byvalue)：

del byvalue[i]
bisect.insort(byvalue, t)

（而其他语句具有O(1)或O(log(N))行为。）

有了更多的经验，他们就克服了 ;-) 这些以“C 速度”发生，除非byvalue增长到数百个元素，否则它通常比花哨的树结构更快 - 并且更节省空间 - 即使它们被编码为优化C。

如果确实变大了，那么从广泛使用的packagebyvalue切换byvalue到使用 a是一个简单的改变。那么没有比 about 更糟糕的陈述了。您的代码部分仍然简单、灵活且易于推理。SortedListsortedcontainersO(log(N))

推荐阅读