Сортировка списка с помощью тем в Java

Question

У меня есть список слов, 1000 слов, я должен перечислить их из наиболее встречающихся наименее встречающихся.

Как:

Dog, 100 times 
Cat, 50 times 
Fish, 40 times 
Monkey, 10 times 
Bird, 10 times 
Camel, 10 times 
. 
. 
. 
Lion, 1 times 
Tiger, 1 times 

Я сделал это и работает с петлей в то время, но это занимает, как 10 секунд, следующая часть задачи является использование темы и сделать сортировку за меньшее время. Я планирую использовать 5 потоков, я могу использовать их и запускать индивидуально, например Thread1 может сортировать 1-200, Thread2 может сортировать 201-400, Thread3 может сортировать 401-600 ... но тогда в конце я бы имел 5 разных списков ? Было бы 10 собак в списке Thread1, 20 собак в списке Thread2 ... Смешанный на консоли ... Я бы хотел, чтобы это было как на примере выше, используя 5 потоков, возможно ли это? Не могли бы вы дать несколько советов, я новичок в Threads.

Редактировать: Я использую встроенную функцию сортировки, пока не важно, какой алгоритм сортировки я использую. Задача состоит не в том, чтобы использовать лучший алгоритм сортировки, а для сортировки с Threads.

Код:

//This is the list 
    ArrayList<String> animalList = new ArrayList<String>(); 

//This is the map from the list 
    Map<String, Integer> map = new HashMap<String, Integer>(); 
    for (String temp : animalList) { 
     Integer count = map.get(temp); 
     map.put(temp, (count == null) ? 1 : count + 1); 
    } 

//This is the final map 
    TreeMap<String, Integer> sortedMap = sortMapByValue(map); 


public static TreeMap<String, Integer> sortMapByValue(Map<String, Integer> map){ 
    Comparator<String> comparator = new ValueComparator(map); 
    TreeMap<String, Integer> result = new TreeMap<String, Integer>(comparator); 
    result.putAll(map); 
    return result; 
} 


public class ValueComparator implements Comparator<String>{ 

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

    public ValueComparator(Map<String, Integer> map2){ 
     this.map.putAll(map2); 
    } 

    @Override 
    public int compare(String s1, String s2) { 
     if(map.get(s1) >= map.get(s2)){ 
      return -1; 
     }else{ 
      return 1; 
     } 
    } 
} 

Answer 1

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

Есть несколько способов избежать этого. Один из них - synchronization. Это (просто), что вы не позволяете другим потокам обращаться к некоторым частям вашего кода до тех пор, пока с ним не будет выполняться другой поток. Это решение может сделать вашу программу завершенной в deadlock. Это не очень поможет вам, так как если вы остановите свои потоки, когда другой скажет сортировку вашего списка, вы ничего не получите от использования потоков.

Что вы можете сделать, это попытаться использовать потоки таким образом, чтобы результат не зависел от порядка выполнения. У вас может быть, например, поток, посвященный первым 200 словам, другому из следующих 200 и так далее. Тогда вы должны комбинировать результаты только в рекурсивном merge-sort, как в моде.

---

Темы - отличный способ улучшить время выполнения программы. Но ... если вам понадобится около 100 секунд, чтобы отсортировать список тысяч слов, ваш алгоритм может быть улучшен.

Что вы можете сделать, это начать с улучшения кода, используя сначала (например, алфавитный) алгоритм сортировки и отсортировать список по имени (вы можете сделать это в O (n · ln (n)), для пример merge-sort, quick-sort или heap-sort). После сортировки списка вам потребуется только O (n), чтобы извлечь ваши частоты, перейдя один раз выше списка, а другой O (m · ln (m)), где m - длина списка частот, чтобы заказать этот список в порядке убывания частоты.

Всего вы могли бы получить свои результаты в O (n · ln (n) + n + m · ln (m)), что в худшем случае - O (2 · n · ln (n) + n) (если два слова не равны). Это все еще O (n · ln (n)).

Все компьютеры могут вычислить что-то порядка О (п · п (п)) менее чем за 100 секунд: P