读入收藏和检索前5 [英] Reading into collection and retrieving top 5

问题描述

我最近在接受采访时问过这个问题。应用程序正在从实时馈送中读取报价和交易量，
例如AAPL 1000，TWTR 500，MSFT 500，AAPL 500 ...
所以，AAPL总体积= 1500等。
我必须将这些读入集合并返回前5个卷。

I was asked this recently in an interview. Application that is reading ticker and trade volume from a live feed, E.g. AAPL 1000, TWTR 500, MSFT 500, AAPL 500 ... So, AAPL total volume = 1500 and so on. I have to read these into a collection and return the top 5 by volume.

我建议在存储时使用哈希映射，然后排序或使用一个树形图。
任何其他更有效率的方法？

I had suggested to use a hash map when storing and then sort or use a Treemap. Any other way that is more efficient?

推荐答案

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

Assuming ticker symbol and trade volume are stored together in an instance of some class TickerAndTradeVolume, you could have references to objects contained in multiple data structures.

因此，散列图可能具有股票代码作为关键字，而TickerAndTradeVolume作为值。然后引用TickerAndTradeVolume实例也可以存储在优先级队列中。每次卷更新时，实例都重新插入到PQ中。

So a hash map may have ticker symbol as key and TickerAndTradeVolume as value. Then references to TickerAndTradeVolume instances can also be stored in a priority queue. Instances are re-inserted into the PQ on every volume update.

按体积排序的前n个字段总是可用于log（n）摊销时间复杂度，以按交易量保持优先级，这比渐次通过Treemap时间排序更快。

The top n by volume are always available in log(n) amortized time complexity to maintain priorities by trade volume, which is asymptotically faster than sorting via Treemap time and again.

这样的东西

    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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！