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

Question

证券交易所(以非常高的速度)以股票代码、买入/卖出对(例如 YHOO，300)的形式出现了一系列股票更新。我们必须始终显示在任何给定时间点交易量排名前 5 位的股票。您将如何在内存中维护这些值？

我的想法是使用 hashmap(Ticker->Volume) 从 feed O(1) 更新我们的数据存储。然后根据交易量创建一个 Treemap 来显示前 5 只股票 O(1)。但我无法想出的是一种有效的方法来同步 Treemap 数据，因为 hashmap 中的值发生变化(非常频繁)。有什么建议吗？

Answer 1

如果交易次数是一个不断增加的累积值(看起来确实如此)，您可以保持:

• 用于更新交易数量的 HashMap ，复杂度为 O(1)。
• 一个包含 5 个元素的简单数组，代表前 5 个代码及其交易量。

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

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

---

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

• 用于保存代码卷更新的 HashMap (代码 -> 卷)。
• 对于前 5 名，您需要使用按体积递减排序的堆。

当更新到达时，您将:

1. 从 hashmap 中获取 ticker 的 Volume 的先前值(如果有的话)，复杂度为 O(1)
2. 在 O(log n) 中从堆中删除旧值(如果存在)，按旧卷查找
3. 在 O(log n) 中将新值添加到堆中
4. 在 O(1) 中更新 hashmap 中的新值

总复杂度为 O(log n)，其中“n”是代码的数量。

即使您需要前 5 个代码，当一个代码的交易量下降时，您也需要找到第 6 个元素将变为第 5 个，然后是第 7 个元素......等等。如果交易数量不是单调的，我认为您的复杂度不会比 O(log n) 低很多。