3

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

4

2 回答 2

0

除了 ，我不能提出任何建议TreeSet，但我可以指出一个可能的优化 - 似乎任何低于迄今为止第 N 个报价的报价根本不需要添加。这意味着树的大小最多为 N，而不是无界。

例如：

final int n = ...;
final NavigableSet<Quote> topNQuotes = new TreeSet<Quote>();

void addQuote(Quote quote) {
    //if the Set of quotes has reached N,
    if (topNQuotes.size() == n) {
        //get the greatest Quote that is less than this one
        Quote lowerQuote = topNQuotes.lower(quote);
        //if no such Quote was found in the Set, quit without adding
        if (lowerQuote == null) {
            return;
        }
        //otherwise remove and discard the lowest Quote from the Set
        topNQuotes.pollFirst();
    }
    //add the new Quote to the Set
    topNQuotes.add(quote);
}

请注意，此示例不是线程安全的。

于 2012-10-18T05:59:16.920 回答
0

从编写实时价格馈送的个人经验来看，如果速度是一个问题，那么占用一些额外的内存是值得的。老实说，如果可行的话，我会建议按价格或订单 ID 对您的价格信息进行散列。

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

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

于 2012-10-18T06:55:06.503 回答