获取TreeMap中的三个最大值

Question

我正在尝试查找TreeMap中的三个最高值。我写了一段代码，就是这样做的，但我想问一下，您是否可以建议一种更有效的方法。基本上，我将文本中的每个单词以及它在文本中出现的次数保存在TreeMap中。然后我使用一个比较器对这些值进行排序。然后，我迭代新创建的Map，直到最后三个值，它们是排序后的最高值，并将它们打印出来。我将使用大文本，所以这不是一个很好的方法。下面是我的代码：

class Text{
    public static void main(String args[]) throws FileNotFoundException, IOException{
        final File textFile = new File("C://FileIO//cinderella.txt"); 
        final BufferedReader in = new BufferedReader(new FileReader(textFile));                               
        final TreeMap<String, Integer> frequencyMap = new TreeMap<String, Integer>(); 

        String currentLine; 
        while ((currentLine = in.readLine()) != null) {  
            currentLine = currentLine.toLowerCase();  
            final StringTokenizer parser = new StringTokenizer(currentLine, " \t\n\r\f.,;:!?'"); 
            while (parser.hasMoreTokens()) { 
                final String currentWord = parser.nextToken(); 
                Integer frequency = frequencyMap.get(currentWord); 
                if (frequency == null) { 
                    frequency = 0; 
                } 
                frequencyMap.put(currentWord, frequency + 1);
            } 
        }  

        System.out.println("This the unsorted Map: "+frequencyMap);

        Map sortedMap = sortByComparator(frequencyMap);
        int i = 0;
        int max=sortedMap.size();
        StringBuilder query= new StringBuilder();

        for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
            Map.Entry<String,Integer> entry = (Map.Entry<String,Integer>) it.next();
            i++;
            if(i<=max && i>=(max-2)){
                String key = entry.getKey();
                //System.out.println(key);
                query.append(key);
                query.append("+");
            }
        }
        System.out.println(query);
    }

    private static Map sortByComparator(TreeMap unsortMap) {
        List list = new LinkedList(unsortMap.entrySet());

        //sort list based on comparator
        Collections.sort(list, new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Comparable) ((Map.Entry) (o1)).getValue())
                       .compareTo(((Map.Entry) (o2)).getValue());
            }
        });

        //put sorted list into map again
        Map sortedMap = new LinkedHashMap();
        for (Iterator it = list.iterator(); it.hasNext();) {
            Map.Entry entry = (Map.Entry)it.next();
            sortedMap.put(entry.getKey(), entry.getValue());

        }
        return  sortedMap;
    }   
}

Answer 1

我会使用哈希图计算频率，然后循环遍历所有频率，选择前3个。这样可以最小化比较，并且永远不需要排序。使用Selection Algorithm

-edit，维基百科页面详细介绍了选择算法的许多不同实现。具体地说，只需使用有界优先级队列，并将大小设置为3。不要花哨地将队列实现为堆或其他任何东西。只需使用数组即可。

Answer 2

如果你真的想要一个可扩展的闪电般的解决方案，请看看Lucene，因为这类事情是它早上起床前做的事情。您所要做的就是为包含所有文本的单个文档建立索引，然后检索排名靠前的术语。有一段代码可以找到排名最靠前的术语，其中包含一个PriorityQueue。我在Clojure中有一个副本，即使您不了解该语言，您也可以从其中收集相关的API调用(或者至少通过google搜索并找到Java版本)：

(defn top-terms [n]
  (let [f "field-name"
        tenum (-> ^IndexSearcher searcher .getIndexReader (.terms (Term. f)))
        q (proxy [org.apache.lucene.util.PriorityQueue] [] 
            (lessThan [a b] (< (a 0) (b 0))))]
    (-> org.apache.lucene.util.PriorityQueue
        (.getDeclaredMethod "initialize" (into-array [Integer/TYPE]))
        (doto (.setAccessible true)) (.invoke q (into-array [(Integer/valueOf n)])))
    (loop [] (when (= (-> tenum .term .field) f)
               (.insertWithOverflow q [(.docFreq tenum) (.term tenum)])
               (when (.next tenum) (recur))))
    (loop [terms nil] (if (> (.size q) 0) (recur (conj terms (.pop q))) terms))))