读入集合并检索前 5 名

Question

我最近在接受采访时被问到这个问题。从实时信息流中读取代码和交易量的应用程序，例如。 AAPL 1000、TWTR 500、MSFT 500、AAPL 500 ... 所以，AAPL 总量 = 1500 等等。我必须将这些读入一个集合中，然后 return 按数量排在前 5 位。

我曾建议在存储时使用散列图，然后进行排序或使用树图。还有其他更有效的方法吗？

Answer 1

假设股票代码和交易量一起存储在某个 class TickerAndTradeVolume 的实例中，您可以引用包含在多个数据结构中的对象。

所以散列映射可以将股票代码作为键，将 TickerAndTradeVolume 作为值。然后对 TickerAndTradeVolume 实例的引用也可以存储在优先队列中。每次卷更新时，实例都会重新插入到 PQ 中。

在 log(n) 摊销时间复杂度中始终可用按交易量排名前 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;
    }

读入集合并检索前 5 名

Reading into collection and retrieving top 5

collections