Самый простой способ сортировки списка слов по происхождению

Question

Какой самый лучший / самый простой способ сортировки большого списка слов (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 - список всех строк. Мне приходилось хранить количество раз, когда каждое слово встречалось в отдельном массиве, потому что я не мог придумать лучшего способа сохранить их в паре, не делая каждое слово отдельным объектом.

Answer 1

Создание HashMap<String, Integer> сопоставления слов с количеством вхождений. В первый раз, когда вы видите слово, добавьте его на карту и установите счетчик на 1. Каждый раз после этого, если слово уже существует на карте, увеличивайте счет.

Это будет намного быстрее, так как вам придется перебирать список слов только один раз. Это разница между O ( n ) и O ( n ² ), что для большого словаря будет огромной разницей.

В конце вы можете взять список слов и отсортировать их по количеству. Для этого вам придется вынуть их из карты и добавить в отдельную структуру данных. (Подсказка: вы можете использовать TreeSet с пользовательским Comparator, который сравнивает слова на основе их частоты. Или, не так элегантно, добавить их к List, а затем sort этот список, опять же с пользовательским Comparator.)

Answer 2

Multiset - это то, что вы ищете из коллекций Google. Эта структура данных точно создана для поддержки ваших вариантов использования. Все, что вам нужно сделать, это заполнить его своими словами. Это будет поддерживать частоту для вас

Answer 3

Почему все так сложно? Вам нужно в основном следующее:

1. Сортировка слов на месте. Теперь те же слова будут сгруппированы.
2. Пройдите по массиву, посчитав дубликаты, и сохраните полученные пары (слово, количество вхождений) в другом массиве
3. Сортировка другого массива по количеству вхождений.

Сложность O (n log n).

Answer 4

Рассматривали ли вы использование интернирования String в дополнение к hashmap? Интернирование строк означает, что все одинаковые строки используют одну и ту же ячейку памяти для экономии памяти. Основываясь на ответе Сортируйте карту по значениям (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
    }

}

}

Answer 5

Самый простой способ сортировки слов - по алфавиту. Но вы также можете сделать это по тому, сколько букв в этом слове есть в другом слове.

Answer 6

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

}