假设有一个带有时间戳的键值对流，我们希望找到最近一个小时内具有最高值的前10个键。（键在最后一个小时内的值是该特定键流式传输的所有值的总和）。
我尝试并想出了一个解决方案，看起来像：http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/。但我无法将时间带入画面，而不让我在时间复杂性上付出沉重代价。欢迎提出任何想法。
要获得精确的在线算法，您需要所有内容的多个副本。您需要按值跟踪排序数据结构中的键，如红黑树。您需要按关键字跟踪，即任何快速关键字查找中的值-散列会起作用。你需要一些观察的事件循环/队列，这样你就可以删除超过一个小时的东西。
这样，添加观察结果的过程看起来像：
- 删除当前要删除的所有观察结果。（稍后将详细介绍如何做到这一点。）
- 将观察添加到要删除的队列中，并使用时间戳将其删除
- 按键，在按键的值的哈希中查找当前总值
- 通过值+键，找到平衡二叉树中的条目，并将其删除
- 按键更新值的哈希中的当前总值
- 按键在值的哈希中插入新值
要找到前10名，你需要遵循类似的路径。
- 删除当前要删除的所有观察结果。（稍后将详细介绍如何做到这一点。）
- 在平衡二叉树中查找前10个观测值
以及删除当前要删除的观察结果，而要删除队列中的顶部元素已超过一个小时：
- 从中弹出一个键/值对以删除队列
- 按键查找总值哈希中的值
- 从平衡二叉树中删除该值
- 按键更新总值哈希中的总值
- 将新的值/键插入平衡的二进制键中
好的，那么成本和时间是多少？
我们把每一份观察结果复印3份。有些是在具有开销的复杂数据结构中。因此，我们使用的空间可能是最后一小时活动的5倍。每次观测有很多运算，但它们都是对数的。事实上，每次观测的总工作量与O(log(n))一样，既用于保持数据结构的最新性，也用于返回前10名。
现在，如果开销太大，简单的解决方案是使其近似。有很多近似算法，但最简单的方法是使数据结构中的包含是随机的。例如，你可以说，任何值超过100的东西都会以其值的1%被包括在内，而任何值低于100的东西的值都是其被包括在内的几率百分比。然后将最终答案乘以100。如果平均值在1-10的范围内，则O(1)滤波器刚刚去除了90-99%所需的数据存储和工作。但你会得到大致的答案，应该没问题。