algorithm - 如何设计一个系统以在时间窗口中查找前 K 个热门帖子

Question

我正在处理一个系统设计问题，我需要在 5 分钟、1 小时和 24 小时窗口内显示前 K 个热门帖子。

我了解通过使用散列图来跟踪频率和使用堆按频率对 K 项进行排序来查找 Top K 元素的方法。

但是，我不确定如何计算时间分量。我一直在阅读有关桶/计数器等的信息，但我无法提出解决方案。

在弄清楚如何以分布式方式构建它之前，我希望先了解该算法。

非常感谢！

标签： algorithmsystem-design

Answer 1

您可以使用自平衡二叉搜索树而不是堆：对于堆允许的所有操作，它们具有相同的时间和空间复杂性，但也允许在 O(log n) 时间内删除元素（而不是 O(n ） 时间）。大多数语言使用这些树实现某种“有序字典”容器抽象；在 C++ 中，它被称为map<T, U>.

对于每个时间窗口，维护一个单独的树。让我们考虑具体的 5m 窗口。

每当有新元素到达时，将其添加到树中，并安排一个 5 分钟的计时器再次将其移除；插入和删除的成本分别为 O(log n)，其中 n 是树增长到的最大大小——即 5 分钟窗口内发生的最大事件数。要找到前 k 个项目，只需开始树的中序遍历，并在报告 k 个项目后停止。这需要 O(k) 时间，并且允许对 k 进行不同的选择。确保您或您的语言的底层容器实现允许并发修改容器。

这种方法很简单，但是为每个新元素安排一个计时器可能会产生很多开销。您也可以“懒惰地”执行删除：当新元素 xNew 在时间 tNew 到达时，像往常一样将 xNew 添加到树中，但不是调度计时器，而是：

1. 将 (xNew, tNew) 添加到单独的 FIFO 队列。
2. 从队列中提取元素 (x, t) 直到 t >= tNew - 5。