在TreeMap中獲取三個最高值

我正試圖在TreeMap中找到三個最高值。我寫了一個這樣的代碼，但我想問你是否可以建議一個更有效的方法。基本上，我將我的文本的每個單詞保存在一個TreeMap中，以及它在文本中出現的次數。然後我使用比較器對值進行排序。然後我遍歷新創建的Map，直到達到最後三個值，這是排序後的最高值並將其打印出來。我將使用大文本，所以這不是一個好方法。這裏是我的代碼：在TreeMap中獲取三個最高值

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; 
    } 
}

來源

2012-05-20 curious

我也要算一個哈希表的頻率，然後遍歷所有這些，選擇前3名。您減少的比較就這樣了，從來沒有進行排序。使用Selection Algorithm

-edit，維基百科頁面詳細說明了選擇算法的許多不同實現。具體而言，只需使用有界的優先級隊列，並將大小設置爲3.不要幻想並將隊列實現爲堆或任何東西。只需使用一個數組。

來源

2012-05-20 19:14:47 goat

避免排序因爲你是「將要使用大量文本」_是有道理的。所以如果你不需要排序進行進一步處理，我會選擇這個解決方案。 – Kai

感謝您的建議。這正是我修改我的代碼的方式。 – curious

如果你真的想要一個可擴展的閃電般的解決方案，請看看Lucene，因爲這種事情是在早上起牀前做的。您只需使用所有文本索引單個文檔，然後檢索頂級條款。有一段代碼可以找到頂級條款，涉及PriorityQueue。我有Clojure中的一個副本，即使你不知道的語言，你可以蒐集從它相關的API調用（它們或至少谷歌，並找到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))))

來源

2012-05-20 19:59:53

感謝Marko。我會看看Lucene，但爲了我目前的目的，Hash地圖更合適，更容易:) – curious

在TreeMap中獲取三個最高值

回答

相關問題