Python Deque - 10 分钟的数据

Question

我正在尝试编写一个脚本，该脚本在执行时会附加一条新的可用信息并删除超过 10 分钟的数据。

我想知道在性能方面跟踪每个信息元素的具体时间同时删除超过 10 分钟的数据的最有效方法是什么。

我的新手想法是将带有时间戳的信息 - [info, time] - 附加到双端队列，并在 while 循环中不断评估双端队列的末尾以删除超过 10 分钟的任何内容......我怀疑这是最好的方法。

谁能举个例子？谢谢。

Answer 1

实现此目的的一种方法是使用以时间戳为关键字的排序树结构。然后你可以找到第一个元素 >= 10 分钟前，并删除之前的所有内容。

使用 bintrees库作为示例(因为它的键切片语法使它非常容易读写......):

q = bintrees.FastRBTree.Tree()
now = datetime.datetime.now()
q[now] = 'a'
q[now - datetime.timedelta(seconds=5)] = 'b'
q[now - datetime.timedelta(seconds=10)] = 'c'
q[now - datetime.timedelta(seconds=15)] = 'd'

now = datetime.datetime.now()
del q[:now - datetime.timedelta(seconds=10)]

这将删除所有内容，但不包括 now-10s，它应该是 c 和 d。

这样，找到要删除的第一个元素需要 log N 时间，并且删除低于该元素的 N 个元素应该是平均情况分摊 log N 但最坏情况 N。因此，您的整体最坏情况时间复杂度不会提高，但您的一般情况下。

当然，管理树而不是双端队列的开销非常高，如果您处理的是一个非常小的队列，那么管理开销很容易高于 N/log N 步骤的节省。

---

还有其他映射更合适的对数数据结构，比如pqueue/heapqueue(由stdlib中的heapq实现)，或者时钟环；我只是选择了一棵红黑树，因为(使用 PyPI 模块)它是最容易演示的树。