时间戳

首页 > 解决方案 > 有效计算给定时间范围内的独立事件

algorithm - 有效计算给定时间范围内的独立事件

问题描述

问题描述

我遇到过这个问题几次，并且一直想知道我的解决方案是否是最佳的，或者（更有可能）有更好的解决方案。

假设我的组件接收由时间和字符串组成的事件。x对于我收到的每个事件，我需要返回在最后几秒钟内看到了多少个独立字符串。（x可配置，但在执行开始时固定）。“最后x几秒钟”是指在具有最高时间戳的事件发生时结束并持续x几秒钟的时间范围（包括两端）。

让我举个例子。我按给定顺序收到以下事件（由该(time, string)对表示），并且对于每个事件，我都会显示预期的返回值，假设x = 5.

我们不能假设事件以正确的顺序出现，但我们可以假设差异很小，即，如果您将事件放在有序列表中，则在大多数情况下，您会将事件添加到列表的末尾或非常接近它。

此外，这里的字符串是一种简化。它们实际上是可以比较相等性和计算哈希值的对象，但不能排序，也不能做花哨的事情。（在剩下的问题中，我仍将这些对象称为“字符串”。）

我的解决方案

我会使用两种数据结构：一个双端队列和一个哈希映射。前者包含按时间顺序排列的事件，后者包含在最后x几秒内看到的字符串以及它们被看到的时间的计数器。

对于收到的每个事件，我会将其添加到队列中并增加地图中的计数器。然后我将移动到队列的开头并从中删除所有那些时间戳太旧（即低于time_of_last_event - x）的事件；对于每个删除的事件，我会减少映射中的相应计数器，如果其计数器为零，则从映射中删除条目。最后，地图的大小是我必须返回的数字。

如果乱序事件经常发生，但事件“几乎是有序的”，我可以考虑使用双链表而不是双端队列；插入事件时，我会从其末端向后搜索以找到插入事件的合适位置。这将使我免于过多的重新分配，但我不确定为我插入的每个事件分配内存是否会在性能方面有所回报。

假设在队列末尾的恒定时间插入，从其开头的恒定时间移除和哈希映射中的恒定时间操作，我会说对该算法的每次调用都将摊销恒定时间（从长远来看，我将删除与我插入一样多的条目，因此平均每次调用一个）。

主要问题是：有没有比所描述的算法更好的算法？ 我说的更好是指运行速度更快或使用更少内存的算法。

还有几个问题

标签： algorithmdata-structures

解决方案

如果您按顺序接收事件，则您的解决方案足够有效，但如果不是，算法将变为二次的，因为在排序位置的双向链表中插入新元素将需要线性时间（就名单）。如果您将x视为常数，这可能不是问题，因为总时间复杂度仍然是O(n)。但是，如果您将x视为一个变量，那么这不是最优的。

解决方案是使用 Min Heap 而不是队列或双向链表：

在堆中插入每个新元素，以时间戳为键。当堆的大小比x大 1 时，删除堆的根，因为它代表与堆中其他x个条目相比最旧的条目。

对于其余部分，您可以像以前一样继续使用哈希映射。

由于堆中的插入和删除具有O(logx)时间复杂度，因此总时间复杂度为O(nlogx)。

推荐阅读