閱讀收集和檢索前5 5

Question

我最近在接受採訪時被問到。應用程序正在讀取來自現場饋送的報價和交易量， E.g. AAPL 1000，TWTR 500，MSFT 500，AAPL 500 ... 所以，AAPL總量= 1500等等。 我必須將它們讀入一個集合中，並返回數量最多的5個。

我曾建議在存儲時使用哈希映射，然後對Treemap進行排序或使用。 任何其他更有效的方式？

Answer 1

假設股票代碼和交易量一起存儲在某個類TickerAndTradeVolume的實例中，則可以引用包含在多個數據結構中的對象。

所以一個哈希映射可能有ticker symbol作爲key和tickerAndTradeVolume作爲value。然後，對TickerAndTradeVolume實例的引用也可以存儲在優先級隊列中。每次卷更新時，實例都會重新插入到PQ中。

按卷數量排名前n總是以log（n）攤銷時間複雜度的形式提供，以保持貿易量的優先級，這比通過Treemap一次次排序的速度更快。

像這樣的事情

Map<String, TickerAndTradeVolume> feed; 
    PriorityQueue<TickerAndTradeVolume> pq; 

    class TickerAndTradeVolume implements Comparable<TickerAndTradeVolume> { 
     private String ticker; 
     private double volume; 

     TickerAndTradeVolume(String ticker, double volume) { 
      this.ticker = ticker; 
      this.volume = volume; 
     } 

     void increaseVolumeBy(double volume) { 
      this.volume += volume; 
     } 

     @Override 
     public int compareTo(TickerAndTradeVolume that) { 
      return (int) (that.volume - this.volume); 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (this == obj) { 
       return true; 
      } 
      if(obj instanceof String) { 
       TickerAndTradeVolume that = (TickerAndTradeVolume) obj; 
       return this.ticker.equals(that.ticker); 
      } 
      return false; 
     } 
    } 

    void addOrUpdateStockVolume(TickerAndTradeVolume tt) { 
     if(!feed.containsKey(tt.ticker)) { 
      feed.put(tt.ticker, tt); 
      pq.add(tt); 
     } 
     else { 
      feed.get(tt.ticker).increaseVolumeBy(tt.volume); 
      // take out and put back in to trigger heap operations 
      pq.remove(feed.get(tt.ticker)); 
      pq.add(feed.get(tt.ticker)); 
     } 
    } 

    List<TickerAndTradeVolume> getTopMaxFive() { 
     List<TickerAndTradeVolume> topFive = new ArrayList<TickerAndTradeVolume>(5); 
     int pqSize = pq.size(); 
     for(int i = 0; i < 5 && i < pqSize; i++) { 
      // poll() takes from the top of the heap 
      topFive.add(pq.poll()); 
     } 
     for(TickerAndTradeVolume tt : topFive) { 
      // put back what we took out 
      pq.add(tt); 
     } 
     return topFive; 
    }