algorithm - 过去一小时内键值对流中的前 10 个

Question

假设有一个带有时间戳的键值对流，我们想找到在过去一小时内具有最高值的前 10 个键。 (过去一小时内的键值是该特定键的所有流式传输值的总和)。

我尝试并提出了一个看起来像这样的解决方案:http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/ .但是我无法在不花费大量时间复杂性的情况下将时间带入画面。任何想法表示赞赏。

Answer 1

要获得精确的在线算法，您将需要所有内容的多个副本。您需要按值跟踪排序数据结构(如红黑树)中的键。您需要按键跟踪任何快速键查找中的值 - 哈希将起作用。你需要某种事件循环/观察队列，这样你就可以删除一个多小时前的东西。

这样，您添加观察的过程如下所示:

1. 删除当前要删除的任何观察结果。 (稍后将详细介绍如何执行此操作。)
2. 将观察添加到要删除的队列中，并带有删除它的时间戳。
3. 通过key，在value的hash中通过key找到当前的总值。
4. 通过value+key，找到平衡二叉树中的表项，并剔除。
5. 通过key更新value散列中的当前总值。
6. 通过键将新值插入值的散列中。

要找到前 10 名，您需要遵循类似的路径。

1. 删除当前要删除的任何观察结果。 (稍后将详细介绍如何执行此操作。)
2. 在平衡二叉树中查找前 10 个观察值。

并删除当前要删除的观察结果，而要删除队列中的顶部元素已超过一小时:

1. 从要删除的队列中弹出一个键/值对。
2. 通过键在总值的散列中找到值。
3. 从平衡二叉树中删除值。
4. 按键更新总值散列中的总值。
5. 将新值/ key 插入平衡二进制 key 。

好的，那么费用和时间是多少？

我们保留每个观察结果的 3 个副本。一些具有开销的复杂数据结构。因此，我们为最后一个小时的事件使用的空间可能是原来的 5 倍。每个观察有很多操作，但它们都是对数的。事实上，每次观察的总工作量与 O(log(n)) 一样，既要保持数据结构最新，又要返回前 10 名。

现在，如果开销变得太多，简单的解决方案是使其近似。有大量的近似算法，但最简单的方法是使数据结构中的内容是随机的。例如，您可以说任何值高于 100 的东西都以其值的 1% 包含在内，而任何值低于 100 的东西都将其值作为被包含的百分比。然后将最终答案乘以 100。如果平均值在 1-10 范围内，则 O(1) 过滤器只是删除了所需数据存储的 90-99%和工作。但是你会得到应该没问题的近似答案。