스레드로 정렬

Question

나는 과제가있어서 작업 코드가 필요합니다. 시작하기 전에 문제를 이해하고 싶지만 쓰기 방법을 파악할 수 없습니다.

가 I 데이터의 배열을, 예

I가 절반이 배열 분할 스레드 풀로 던져 내가 < = 2 요소를 가질 때까지 재귀 적으로 그렇게 할 필요

var arr = new byte[] {5,3,1,7,8,5,3,2,6,7,9,3,2,4,2,1} 

이 걸릴. 만약 내가 2 요소를 가지고 내가 덜 확인하고 왼쪽에 넣어 다음 배열을 반환해야합니다.

내가 이해하지 못하는 것은 어떻게 배열을 병합합니까? 내가 배열을 분할하고, 풀에 스레드를 던져서 준비가 될 때까지 차단한다고 가정합니까? 스레드의 결과는 어떻게 얻을 수 있습니까? 차단하지 않고 배열을 병합 할 수 없다고 가정합니다.

내가 지금까지 무엇을 가지고 있는지.

static void Main(string[] args) 
    { 
     var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 }; 
     var newarr = Sort(arr); 
     Console.Write(BitConverter.ToString(newarr)); 
    } 
    static byte[] Sort(byte[] arr) 
    { 
     if (arr.Length <= 2) 
      return arr; 
     if (arr.Length == 2) 
     { 
      if (arr[0] > arr[1]) 
      { 
       var t = arr[0]; 
       arr[0] = arr[1]; 
       arr[1] = t; 
      } 
      return arr; 
     } 

     var arr1 = arr.Take(arr.Length/2).ToArray(); 
     var arr2 = arr.Skip(arr1.Count()).ToArray(); 
     //?? 
     return arr; 
    } 

참고 : 교수는 다른 사람들에게 도움을 요청할 수 있다고 말했습니다. 나는 묻지 않고이 문제를 해결할 수 있다고 생각하지만 가장 좋은 대답을 원합니다. 스레딩은 내 약점입니다. (db, binary, io, 웹 인터페이스, 복잡한 스레드는 없습니다.)

Answer 1

이것은 merge sort의 병렬 버전 인 것으로 보입니다. 필수적으로 재귀 순차 버전처럼 작동하도록해야하지만 분명히 별도의 작업으로 각 재귀 정렬을 실행하십시오.

작업 API에는 완료를 기다리는 것과 결과를 전달하는 방법이 있어야합니다. 이를 통해 전통적인 mergesort를 상당히 잘 복사 할 수 있습니다. 각 하위 정렬에 대해 작업을 풀에 넣고 두 하위 작업의 완료를 기다립니다. 그런 다음 병합을 수행하고 자신의 결과를 소명하는 작업에 되돌려 보냅니다.

일반 스레드 API 만있는 경우 (즉, 실제 작업 라이브러리가없는 경우), 세 번째 배열에 출력을 제공하는 것이 좋습니다. 각 스레드에는 두 개의 입력 배열과 하나의 출력 배열이 있습니다. 각 태스크에 대해 새로운 스레드를 작성할 수있는 경우, 두 개의 하위 스레드를 결합하여 태스크 완료를 기다릴 수 있습니다.

Answer 2

마틴의 답변에 덧붙이면 어레이의 더 작은 복사본을 만들지 않을 것입니다. 대신 각 스레드는 원래 배열의 하위 집합에서 작동하게됩니다.

Answer 3

기꺼이보다 기꺼이 : Any multi-core sorting implementation in .NET?