如何存储连续的数据流，以便您可以访问最频繁的值？

Question

来自证券交易所(以非常高的比率)的股票更新流以股票代码、买卖对(例如YHOO,300)的形式到来。我们必须始终显示任何给定时间点成交量最大的5只股票。如何在内存中维护这些值？

我的想法是使用一个哈希图(收银机->卷)从提要O(1).And更新我们的数据存储，然后基于卷创建一个Treemap来显示top5股票O(1)。但我不能想到的是，当hashmap中的值(非常频繁地)更改时，同步树状图数据的有效方法。有什么建议吗？

Answer 1

如果交易的数量是一个不断增加的累积值(看起来是这样)，你只需要保持：

• 您的哈希图，用于更新O(1)中的交易数量。
• 由5个元素组成的简单数组，表示前5个股票代码及其成交量。

当新的更新到达时，您可以更新O(1)中的hashmap，如果新的交易数量足够大，可以进入前5名，那么您还可以更新您的数组。检查数组和更新数组可以在O(1)中完成。如果您不想将新卷与所有5个值进行比较，也可以使用二进制搜索。

没有比检查log(5)值的平均值更好的方法了。

如果交易数量不是越来越单调(这似乎不太可能，但如果您想要考虑在有限的时间间隔内完成的交易数量，则可能会发生)，您还可以保持：

• 您的哈希图(Ticker ->卷)用于保存自动收报机卷上的更新。
• 对于前5名，您需要使用按卷递减排序的堆。

当更新到达时，您将：

1. 从O(1)
2. 从O(log )中的堆中删除旧值(如果存在)，按旧卷查找
3. 将新值添加到O(log )中的堆中
4. 更新O(1)

<代码>G221中的哈希图中的新值

总复杂度为O(log )，其中"n“是自动收报机的数量。

即使您需要前5个滚动条，当一个滚动条的音量下降时，您也需要找到第6个元素，它将成为第5个元素和第7个元素。诸若此类。如果交易的数量不是单调的，我不认为你可以在复杂度上比O(log )低很多。

Answer 2

我们可以使用堆数据结构，其中根是交易量最大的股票。它的孩子是交易量第二大的。Root的孙子孙女将会给4号和5号

Answer 3

这是我能想到的三个选项：

• 使用bag收集股票代码，并偶尔对其进行迭代以计算频率。在每天的收盘铃声后，重新设置袋子。这将会起作用，但我怀疑你是否真的想要一天一次的统计数据。

，

• ，我在想，你需要一分钟左右的窗口，这样才能让它真正工作起来。在这种情况下，我会将交易保存在dequeue中。在前面插入新的行业，从后面修剪旧的行业。偶尔冻结它，以计算前五名。这是有效的，但如果事情变得激烈，可能很难预测您可能需要多大的队列。
• 另一种方法是使用某种splay tree。但我不确定它是否比仅仅显示最近五笔交易更好。--