python - Python 中的事件列表

Question

我正在寻找一种有效的方法来解决 Python 中的特定问题。我有一连串的事件到达，每个事件都有一个相关的时间戳。从概念上讲，我将这些事件添加到时间排序列表的末尾，并对它们进行一些处理，对各种计数和平均值进行一些更改(取决于事件的类型)。当我删除列表开头的事件并对我的计数和平均值进行相关调整时，事件会在 15 分钟后超时。 collections 模块中的 deque 类非常适合这个。

现在开始讨论这个问题，我想扩展这个想法，但也保留过去 5 分钟和 1 分钟内事件的计数和平均值。正如我所看到的，我无法在使用单个双端队列的同时有效地使这些时间段内的事件超时。我可以将一对索引保存到下一个事件的双端队列中，以在 5 分钟和 1 分钟的边界超时，但据我了解，索引到双端队列是一个 O(n) 操作。我还可以使用 3 个单独的双端队列，每个时间段一个，每个列表上都有重复的事件(或对事件的引用)。这感觉很丑。

我正在尝试的解决方案是使用链表，但这对于 Python 来说似乎很低级；我认为 Python 不提供链表结构，所以我需要自己编写。还有一些额外的限制，因为有大量的事件并且内存相当有限。对于如何解决此问题的任何其他建议或见解，我将不胜感激。

Answer 1

你可以使用三个双端队列，但像这样:

• 原来的间隔为 1 分钟(而不是 15 分钟)
• 另一个 5 分钟，将接收来自上一个双端队列的事件
• 另一个 15 分钟，将接收来自前一个双端队列的事件。

这样，就没有重复项，也不需要索引。这也可以扩展。