Сортировка ArrayList, приложение stuck

Question

У меня есть ArrayList, заполненный словами из текстового файла, который мне нужно отсортировать по появлению слов, от самых возникающих до менее встречающихся. Я копирую оригинал ArrayList со словами в другой Arraylist, а также добавляю сверху число вхождений. Таким образом, слово в новом ArrayList будет выглядеть, например: «пароль: 125», где «пароль» - это слово, а «125» - количество вхождений в ArrayList.

for (int i=0;i<sorter.size();i++) { 
        sorter2.add(sorter.get(i)+":"+Collections.frequency(sorter, sorter.get(i))); 
       } 

Потом я отсортировать ArrayList с этим классом:

public class RepeatFormulaCounter implements Comparator<String> { 

    @Override 
    public int compare(String o1, String o2) { 
     if (findValue(o2) != findValue(o1)) { 
      return findValue(o2) - findValue(o1); 
     } 
     return o2.compareTo(o1); 
    } 
    public int findValue(String find){ 
     int result=0; 
     String spliter[]=find.split(":");   
     result=Integer.parseInt(spliter[1]); 
     return result; 
    } 


} 

Однако, как у меня есть 5 текстовых файлов, заполненных слов, которые 3 из файлов являются около 45 000 слов и 2 с более чем 1 000 000, файлы с около 45000 слов сортируются и отображаются без каких-либо проблем, но когда я начинаю сортировать те, у которых более 1 000 000 слов, приложение застревает. Почему это происходит? и как я могу это исправить?

Обратите внимание, что я использую приложение GUI для его отображения. И я использую 2 подобных класса сортировки для других способов сортировки по различным критериям, которые отображаются и выполняются без каких-либо проблем.

Answer 1

Почему вы храните слово как "password:125"? Вы работаете очень неэффективно. Вы должны использовать эффективную структуру данных для хранения статистики своего слова. Используйте интерфейс карты и выберите правильную реализацию, чтобы хранить слова с их появлением.

Map<String, Integer> wordsMap = new HashMap<String,Double>(); 

/* Fill the wordsMap with data, then use this function to sort. 
    Fill and update value by key is simple: 

    wordsMap .put(key, 50); <-- put value 
    wordsMap .put(key, map.get(key) + 1); <--- update value 

    For example: 

    wordsMap .put("google", 0); <-- put value 
    wordsMap .put("google", map.get("google") + 1); <--- increment value by 1 

*/ 

public static <K, V extends Comparable<? super V>> Map<K, V> 
    sortByValue(Map<K, V> map) 
{ 
    List<Map.Entry<K, V>> list = 
     new LinkedList<>(map.entrySet()); 
    Collections.sort(list, new Comparator<Map.Entry<K, V>>() 
    { 
     @Override 
     public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) 
     { 
      return (o1.getValue()).compareTo(o2.getValue()); 
     } 
    }); 

    Map<K, V> result = new LinkedHashMap<>(); 
    for (Map.Entry<K, V> entry : list) 
    { 
     result.put(entry.getKey(), entry.getValue()); 
    } 
    return result; 
} 

// sortByValue(wordsMap); 

Кроме того, вы можете прочитать о классах Hashtable, LinkedHashMap, TreeMap, а затем выбрать один с более высокой производительностью. Они реализуют один и тот же интерфейс карты, но имеют разные асимптотики для внутренней реализации методов put(), get() и других методов.

Javadocs от Sun для каждого класса коллекции обычно скажет вам, что именно вы хотите.

HashMap, например:

Этой реализация обеспечивает производительность постоянная времени для основных операций ( получить и положить), предполагая, что хэш-функция рассеивает элементов должным образом среди ведра. Итерация по представлениям коллекции требует времени, пропорционального «емкости» экземпляра HashMap (количество ковшей) плюс его размер (число значений ключа ).

TreeMap:

Эта реализация обеспечивает гарантированную журнала (п) затраты времени для ContainsKey, получить, поставить и удалить операции.

TreeSet:

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

Read more about this.

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

Answer 2

Я думаю, что проблема может быть за пределами показанного кода, но вы можете попытаться уменьшить разбиение объектов, уменьшив количество вызовов на поиск, а затем количество созданных объектов (в настоящее время каждый вызов на поиск создает 3 новых объекта, и вы вызываете найти 4 раза сравнить):

@Override 
public int compare(String o1, String o2) { 
    int f2 = findValue(o2); 
    int f1 = findValue(o1); 
    if (f2 != f1) { 
     return f2 - f1; 
    } 
    return o2.compareTo(o1); 
} 

public int findValue(String find){ 
    int result = 0; 
    int cut = find.lastIndexOf(':'); 
    result = Integer.parseInt(find.substring(cut + 1)); 
    return result; 
} 

Это, вероятно, можно улучшить еще немного, избавившись от подстроки ...

вероятно, лучшим вариантом было бы передать в карте, которую вы используете для подсчета в конструктор компаратора, а затем использовать его в компараторе:

public class CountComparator implements Comparator<String> { 
    Map<String, Integer> counts; 
    public CountComparator(Map<String, Integer> counts) { 
    this.counts = counts; 
    } 

    public int compare(String o1, String o2) { 
    int f2 = counts.get(o2); 
    int f1 = counts.get(o1); 
    if (f1 != f2) { 
     return f2 - f1; 
    } 
    return o2.compareTo(o1); 
    } 
} 

Answer 3

Скорее всего проблема с памятью. Попробуйте увеличить размер кучи jvm. Вы делаете много временных строк, и ваш сборщик мусора сойдет с ума при больших размерах данных.

Answer 4

Используйте потоки, которые были представлены на Java 8. Они отлично подходят для обработки данных.

HashMap<String, Integer> occurences = new HashMap<>(); 
... 
Stream<String> stream = occurences.entrySet().stream() 
    .sorted((a, b) -> b.getValue() - a.getValue()) 
    .map(kv -> kv.getKey()); 
String[] sortedWords = stream.toArray(size -> new String[size]);