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 

내가 이런 짓을하고 while 루프와 함께 작동하지만, 10 초처럼 걸리는 작업의 다음 부분은 스레드를 사용하여 적은 시간에 정렬을 확인하는 것입니다. 나는 5 개의 쓰레드를 사용할 계획이다. 나는 그것들을 사용할 수 있고, 개별적으로 달릴 수있다. Thread1은 1-200을, Thread2는 201-400을, Thread3는 401-600을 정렬 할 수 있다고 말하지만, 결국에는 5 개의 다른리스트를 가질 것이다. ? Thread1 목록에 10 개의 Dog가 있고 Thread2 목록에 20 개의 Dog가 있습니다 ... 콘솔에 혼합되어 있습니다 ... 위 예제에서 5 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

는 대부분 자바에서 스레드가 (당신이 코어 당 스레드를하지 않는 한)를 동시에 실행하고 무슨 일하는 흐름이 지속적으로 스레드 사이에 따라서 결과가에 의존하는 경우 변화하고 있다는 것입니다하지 않습니다 작업 순서가 매우 빠르게 예측할 수 없게됩니다.

이 문제를 방지 할 수있는 몇 가지 방법이 있습니다. 그 중 하나는 synchronization입니다. 즉, 다른 스레드가 다른 스레드로 끝날 때까지 다른 스레드가 코드의 일부분을 액세스 할 수 없도록하는 것입니다. 이 솔루션을 사용하면 프로그램이 deadlock이 될 수 있습니다. 이것은 정말 도움이되지 않을 것입니다. 왜냐하면 다른 스레드가 목록을 정렬한다고 말할 때 스레드를 멈추게하면 스레드를 사용하지 않고 아무 것도 얻을 수 없기 때문입니다.

당신이 할 수있는 것은 결과가 실행 순서에 의존하지 않는 방식으로 스레드를 사용하는 것입니다. 예를 들어 처음 200 단어를 처리하는 스레드와 다음 200 단어를 처리하는 스레드를 가질 수 있습니다. 그런 다음 결과를 반복적 인 방식으로 재사용 합쳐야합니다. merge-sort 유행처럼.

---

스레드는 프로그램의 실행 시간을 개선 할 수있는 좋은 방법입니다. 하지만 ... 1000 단어 목록을 정렬하는 데 약 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) (두 단어가 같지 않은 경우). 이것은 여전히 ​​O (n · ln (n))입니다.

모든 컴퓨터는 100 초 이내에 O (n · ln (n)) 차수를 계산할 수 있습니다. P