TopK问题

从文件中输出请求最频繁的10个 HTTP 接口，及其相应的请求数量
数据格式如下

GET /mdc/city/queryAllCities.json?arg1=var1&arg2=var2
GET /twell/public.htm?arg1=var1&arg2=var2
GET /duty/getToDoDutyCount.json?arg1=var1&arg2=var2
GET /notification/queryMessageByUid.htm?arg1=var1&arg2=var2
GET /twell/querytwellDetailForMobile.htm?arg1=var1&arg2=var2
GET /twell/public.htm?arg1=var1&arg2=var2
GET /twell/private.htm?arg1=var1&arg2=var2
POST /tag/getSearchTagList.json
POST /user/postDeviceInfo.htm

从大数据中找到TopK个数，比较经典的就是维护一个小根堆，堆顶是堆中最小的元素，每次通过移除堆顶，重新堆排序来维护这个结构。
在java中有一种数据结构可以维护一个堆，为PriorityQueue，具体实现暂不深究。
每次判断队列顶端元素和新元素大小决定是否入队，当超过维护的上限时移除堆顶元素。

  public void findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
        for (int num : nums) {
            if (minQueue.size() < k || num > minQueue.peek())
                minQueue.offer(num);
            if (minQueue.size() > k)
                minQueue.poll();
        }
        for(int i=0;i<k;i++){
            System.out.println(minQueue.poll());
        }
    }

对于这道题，一开始想法是用java的hashmap解决，然后用Collections.sort()全部排序取前十

    public static void requestTopK(int k) {
        final HashMap<String, Integer> hashMap = new HashMap();
        try {
            IOUtils.readLines(file_path, new LineProcessor<String>() {
                @Override
                public boolean processLine(String s) throws IOException {
                    String key = s.split(" ")[1];
                    if (hashMap.containsKey(key)) {
                        hashMap.put(key, Integer.valueOf(hashMap.get(key)) + 1);
                    } else {
                        hashMap.put(key, 1);
                    }
                    return true;
                }

                @Override
                public String getResult() {
                    return null;
                }
            });
        } catch (IOException e) {
            e.printStackTrace();
        }
        List<Map.Entry<String, Integer>> list = new ArrayList<>();
        list.addAll(hashMap.entrySet());
        Ordering ordering = Ordering.natural().reverse().onResultOf(new Function<Map.Entry<String, Integer>, Comparable>() {

            @Nullable
            @Override
            public Comparable apply(@Nullable Map.Entry<String, Integer> stringIntegerEntry) {
                return stringIntegerEntry.getValue();
            }
        });
        Collections.sort(list, ordering);
        for (int i = 0; i < k; i++) {
            System.out.println(list.get(i));
        }

    }

但是其实这道题可以结合guava api来做，使用multset数据结构

  public static void requestTopK2(int k) {
        final Multiset multiset = HashMultiset.create();
        try {
            IOUtils.readLines(file_path, new LineProcessor<String>() {

                @Override
                public boolean processLine(String s) throws IOException {
                    String urlContent = s.split(" ")[1];
                    multiset.add(urlContent);
                    return true;
                }

                @Override
                public String getResult() {
                    return null;
                }
            });
        } catch (IOException e) {
            logger.error(e.getMessage());
        }
        findKthLargest(multiset.elementSet(), k, multiset);
    }

PriorityQueue存储String，自定义实现接口Comparator()，multset.count()时间复杂度0(1)，根据String对应的出现次数定义顺序。
另外注意的是，原输出方式是每次移除堆顶输出，但堆顶是堆中最小元素，相当于从小到大输出这十个数。如果从大到小输出可以利用栈结构。

    public static void findKthLargest(Set<String> set, int k, final Multiset multiset) {
        PriorityQueue<String> minQueue = new PriorityQueue<>(k, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return multiset.count(o1) - multiset.count(o2);
            }
        });
        for (String s : set) {
            if (minQueue.size() < k || multiset.count(s) > multiset.count(minQueue.peek())) {
                minQueue.offer(s);
            }
            if (minQueue.size() > k) {
                minQueue.poll();
            }
        }
        Stack<String> stack = new Stack();
        for (int i = 0; i < k; i++) {
            String poll = minQueue.poll();
            stack.push(poll);
        }
        for (int i = 0; i < k; i++) {
            String url = stack.pop();
            System.out.println(url + " " + multiset.count(url));
        }
    }

通过multset这种结构重新设计findKthLargest()方法时更简单了一点。如果是List<Map.Entry<String, Integer>>形式的话，实现的代码非常长也非常难看。