最簡單的方式來按字號排序字詞列表

什麼是排序大量字詞列表（10,000-20,000）的最佳/最簡單的方式是按列表中出現的次數（Java）排序。我嘗試了一個基本的實現，但我得到了一個內存不足的運行時錯誤，所以我需要一個更有效的方法。你會建議什麼？最簡單的方式來按字號排序字詞列表

ArrayList<String> occuringWords = new ArrayList<String>(); 
    ArrayList<Integer> numberOccur = new ArrayList<Integer>(); 
    String temp; 
    int count; 
    for(int i = 0; i < finalWords.size(); i++){ 
     temp = finalWords.get(i); 
     count = 0; 
     for(int j = 0; j < finalWords.size(); j++){ 
      if(temp.equals(finalWords.get(j))){ 
      count++; 
      finalWords.remove(j); 
      j--; 
      } 
     } 
     if(numberOccur.size() == 0){ 
      numberOccur.add(count); 
      occuringWords.add(temp); 
     }else{ 
      for(int j = 0; j < numberOccur.size(); j++){ 
      if(count>numberOccur.get(j)){ 
       numberOccur.add(j, count); 
       occuringWords.add(j, temp); 
      } 
     } 
    } 
}

其中，finalWords是所有字符串的列表。我必須將每個單詞出現的次數存儲在單獨的數組列表中，因爲我想不出讓每個單詞成爲單獨對象的更好方法。

來源

2010-03-02 GuyNoir

C＃LINQ將使它沒有道理的！請參閱http://stackoverflow.com/questions/454601/how-to-count-duplicates-in-list-with-linq 它使用弗拉德的算法。雖然，不是hashmap。 – Fakrudeen 2010-03-03 06:42:11

Multiset是你正在從谷歌收藏搜索。該數據結構完全是爲支持您的用例而構建的。你所需要做的就是用你的話填充它。它會保持你的頻率

來源

2010-03-03 02:11:50

+1同意簡單的解決方案。 – gpampara 2010-03-03 06:26:22

+1谷歌的集合，雖然現在它包含在谷歌番石榴： http://code.google.com/p/google-collections/ http://code.google.com/p/guava-libraries/ – 2010-03-03 08:53:34

構建一個HashMap<String, Integer>映射字到出現次數。您第一次看到一個單詞時，將其添加到地圖中，並將計數設置爲1.此後，如果該單詞已經存在於地圖中，則每次都會增加計數。

這樣會快得多，因爲您只需遍歷一次單詞列表。這是O（ n）與O（ n ）之間的差異，這對於大型字典來說將是一個巨大的差異。

最後，您可以拿出單詞列表並按count數對它們進行排序。您必須將它們從地圖中取出並將其添加到單獨的數據結構中才能執行此操作。（提示：你可以使用TreeSet使用自定義Comparator了基於它們的頻率進行比較的話，或較少優雅，帶有自定義Comparator將它們添加到List然後sort該列表，再次）

來源

2010-03-02 20:21:59

如果您的內存不足，請嘗試查看是否可以爲JVM提供更多內存。使用-Xmx和和-Xms選項來獲取最大和初始內存。僅僅因爲你得到一個OutOfMemoryException並不意味着你沒有物理內存。 – phisch 2010-03-02 20:23:35

@John Kugelman：你如何在它的值上對Map 進行排序？ – SyntaxT3rr0r 2010-03-02 20:25:55

@Wizard：迭代你地圖<字符串，整數>，並將它們添加到地圖<整數，字符串>與計爲關鍵。然後通過鍵迭代產生的地圖。 – 2010-03-02 20:31:37

爲什麼都這麼複雜？您基本上需要以下內容：

對單詞進行就地排序。相同的單詞現在將被分組。
檢查數組，計算重複項並將結果對（字數，出現次數）存儲在其他數組中
按出現次數排序另一個數組。

複雜度爲O（n log n）。

來源

2010-03-02 20:29:28 Vlad

也是一個很好的答案。這可能比我的答案更快或更慢，具體取決於有多少重複。我相對較少，這樣會更好，因爲它會避免額外的數據結構;如果有很多，那麼我的排序將消除重複，這將節省時間。 – 2010-03-02 20:48:21

public List<String> countOccurences(ArrayList<String> list){ 
    HashMap<String, Integer> hm = new HashMap<String, Integer>(); 
    for (String s:list) { 
    Integer i = hm.get(s); 
    if (i == null){ 
     i = 0; 
    } 
    i++; 

    hm.put(s, i); 
    } 


    List<String> mapKeys = new ArrayList<String>(hm.keySet()); 
    List<Integer> mapValues = new ArrayList<Integer>(hm.values()); 
    HashMap<String, Integer> sortedMap = new LinkedHashMap<String, Integer>(); 
    TreeSet<Integer> sortedSet = new TreeSet<Integer>(mapValues); 
    Object[] sortedArray = sortedSet.toArray(); 
    int size = sortedArray.length; 
    for (int i=0; i<size; i++){ 
    sortedMap.put(mapKeys.get(mapValues.indexOf(sortedArray[i])), 
        (Double)sortedArray[i]); 
    } 
    return new ArrayList<String>(sorted.keyset()); 

}

來源

2010-03-02 20:33:14 Paul

PS。我沒有測試過......只是寫出來了。 – Paul 2010-03-02 20:33:34

-2

最簡單的方法來排序你的話是按字母順序。但是，您也可以通過另一個詞中存在多少個字母來實現。

來源

2013-01-29 17:15:25 user2022567

你有沒有考慮過使用String interning除了hashmap？字符串interning意味着所有相同的字符串使用相同的內存位置以節省內存。基於答案Sort a Map<Key, Value> by values (Java)請參閱以下內容：

import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.TreeMap; 
public class WordOccurSortExample { 

public static void main(String[] args) { 
     new WordOccurSortExample();   
} 

public WordOccurSortExample() 
{ 
    ArrayList<String> occuringWords = new ArrayList<String>(); 
    occuringWords.add("Menios".intern()); 
    occuringWords.add("Menios".intern()); 
    occuringWords.add("Menios".intern()); 
    occuringWords.add("Menios".intern()); 
    occuringWords.add("Moo".intern()); 
    occuringWords.add("Moo".intern()); 
    occuringWords.add("Moo".intern()); 
    occuringWords.add("Moo".intern()); 
    occuringWords.add("Moo".intern()); 
    occuringWords.add("Boo".intern()); 
    occuringWords.add("Boo".intern()); 
    occuringWords.add("Boo".intern()); 

    HashMap<String, Integer> occurances = new HashMap<String, Integer>(); 

    Iterator<String> it = occuringWords.iterator(); 
    String word; 
    Integer count; 
    while(it.hasNext()) 
    { 
     word = it.next(); 

     if((count = occurances.get(word))==null) 
     occurances.put(word, 1); 
     else 
     occurances.put(word, new Integer(count+1)); 
    }  

    ValueComparator bvc = new ValueComparator(occurances); 
    TreeMap<String,Integer> sorted_map = new TreeMap<String,Integer>(bvc); 

    System.out.println("unsorted map: "+occuringWords); 
    sorted_map.putAll(occurances); 
    System.out.println("results: "+sorted_map); 
} 


class ValueComparator implements Comparator<String> { 

    HashMap<String, Integer> base; 
    public ValueComparator(HashMap<String, Integer> base) { 
     this.base = base; 
    } 

    // Note: this comparator imposes orderings that are inconsistent with equals.  
    public int compare(String a, String b) { 
     if (base.get(a) >= base.get(b)) { 
      return -1; 
     } else { 
      return 1; 
     } // returning 0 would merge keys 
    } 

}

}

來源

2013-04-09 19:01:16

最簡單的方式來按字號排序字詞列表

回答

相關問題