TopK问题

短命女 2021-09-15 06:50 449阅读 0赞

从文件中输出请求最频繁的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>>形式的话，实现的代码非常长也非常难看。