java - 饲料数据结构

Question

就目前情况而言，这个问题不太适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、民意调查或扩展讨论。如果您觉得这个问题可以改进并可能重新开放， visit the help center以获得指导。

已关闭 10 年前。

最适合以下场景的数据结构是什么:需要整理股票报价(股票代码、价格)。每小时，需要按降序报告前 N 个股票(最高报价)。潜在的，一小时内的报价数量可能达到数百万。由于频繁的插入，带有比较器的数组列表将是一场灾难。TreeSet 似乎是一种选择 - 但有人可以建议更好的结构(如果有的话)。(这可以包括构建通用数据结构，而不是使用现有的 java 集合类。)

Answer 1

根据编写实时价格反馈的个人经验，如果速度是一个问题，那么占用一些额外的内存是值得的。如果可行的话，我真诚地建议通过价格或订单 ID 对您的价格 Feed 进行哈希处理。

此外，如果我理解正确的话，您想要显示某个交易品种的前 N ​​个价格。虽然这 N 个价格可能有数百万个订单，但它们都可以整理为 N 个价格水平之一。因此，如果您创建一个价格水平对象，您的数据结构只需围绕指向这些价格水平对象的指针进行洗牌。在这种情况下，只要 N 不太大(因为特定交易品种通常没有那么多价格水平)，数组在局部性方面可能会足够快。

我还认为，如果您不想散列它，那么使用循环数组将是显示价格水平书籍的一个不错的解决方案。这样，前端(即最低价格)和末尾(最高价格)的插入平均时间应该是恒定的。您还可以使用影子数组来确保 O(1) 常数时间插入。