最简单的方式来按字号排序字词列表

什么是排序大量字词列表（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

最简单的方式来按字号排序字词列表

回答

相关问题