股票供稿數據結構

Question

什麼是以下場景中最合適的數據結構： 需要整理股票報價（代碼代碼，價格）。每小時，需要獲得最高N個報酬（最高報價）按降序報道。 潛在地，報價的數量可以在一小時內達到數百萬。 帶有比較器的ArrayList會因頻繁插入而成爲災難。 TreeSet似乎是一種選擇 - 但是有人可能會提出一個更好的結構，如果有的話。 （這可以包括建立在通用數據結構上，而不是使用現有的java集合類。）

Answer 1

我不能建議除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); 
} 

注意，這個例子是不是線程安全的。

Answer 2

從編寫實時價格飼料的個人經驗來看，如果速度是一個問題，它是值得它佔用一些額外的記憶。如果可行，我會誠實地建議用價格或訂單ID對價格進行散列。另外，如果我理解正確，您想顯示符號的前N個價格。雖然可能有數百萬個訂單超過這些N價格，但它們可以分別整理成N個價格水平之一。因此，如果您製作價格水平對象，那麼您的數據結構只需要對這些價格水平對象的指針進行洗牌。在這種情況下，只要N不是太大（因爲某個特定符號的價格水平通常不會太高），那麼數組可能足夠快且具有局部性。

我也會認爲如果你不想散列它，使用圓形數組將是一個體面的解決方案來顯示價格水平的書。這樣，在前面插入（即最低價格）和結束（最高）的平均時間都應該是恆定的。您還可以使用陰影陣列來確保O（1）常量時間插入。