Easiest Way to Sort a List of Words by Occurance

Question

What is the best/easiest way to sort a large list of words (10,000-20,000) by the number of times they occur in the list, in Java. I tried a basic implementation but I get an out of memory runtime error, so I need a more efficient way. What would you suggest?

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

Where finalWords is the list of all of the Strings. I had to store the number of times each word occured in a separate arraylist because I couldn't think of a better way to keep them paired without making each word a separate object.

Answer 1

Build a HashMap<String, Integer> mapping words to the number of occurrences. The first time you see a word add it to the map and set the count to 1. Every time thereafter if the word already exists in the map increment the count.

This will be much faster since you will only have to iterate over the list of words once. It's the difference between O(n) and O(n²), which for a large dictionary will be a tremendous difference.

At the end you can then take the list of words and sort them by count. You'll have to take them out of the map and add them to a separate data structure to do this. (Hint: you could use a TreeSet with a custom Comparator which compares words based on their frequency. Or, less elegantly, add them to a List and then sort that list, again with a custom Comparator.)

Answer 2

Why all so complicated? You need basically the following:

1. Sort the words in-place. The same words will be grouped now.
2. Go through the array, counting duplicates and store the resulting pairs (word, number of occurrences) in other array
3. Sort the other array by number of occurrences.

The complexity is O(n log n).

Answer 3

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());

}

Answer 4

The Multiset is what you are looking from google collections. That data structure is exactly built to support your use cases. All you need to do is populate it with your words. It will maintain the frequency for you