이 병렬 정렬 병합이 올바르게 구현 되었습니까?

Question

병렬 병합 정렬이 올바르게 구현 되었습니까? 그것은 정확하게 보이고, 나는 시험을 쓰기 위하여 40seconds를 가지고 가고 hasnt는 실패했다.

요점은 그 때마다 반으로 배열을 나눠서 정렬해야합니다. 그럼 내가 잘못 가고 asked a question for a sanity check (내 자신의 온전한)되었는지 확인하려고. 나는 in place sort을 원했지만 대답을 볼 때 복잡하다는 결론을 내 렸습니다. 그래서 아래를 구현했습니다.

4 바이트 배열을 정렬하지만 스레딩을 배우기 위해 작업/스레드를 생성 할 필요가 없습니다. 이 문제를 개선하기 위해 무엇인가 잘못되었거나 바뀔 수 있습니다. 내게는 완벽 해 보이지만 일반적인 의견을 원합니다.

static void Main(string[] args) 
{ 
    var start = DateTime.Now; 
    //for (int z = 0; z < 1000000; z++) 
    int z = 0; 
    while(true) 
    { 
     var curr = DateTime.Now; 
     if (curr - start > TimeSpan.FromMinutes(1)) 
      break; 
     var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 }; 
     Sort(arr, 0, arr.Length, new byte[arr.Length]); 
     //Console.Write(BitConverter.ToString(arr)); 
     for (int i = 1; i < arr.Length; ++i) 
     { 
      if (arr[i] > arr[i]) 
      { 
       System.Diagnostics.Debug.Assert(false); 
       throw new Exception("Sort was incorrect " + BitConverter.ToString(arr)); 
      } 
     } 
     ++z; 
    } 
    Console.WriteLine("Tried {0} times with success", z); 
} 
static void Sort(byte[] arr, int leftPos, int rightPos, byte[] tempArr) 
{ 
    var len = rightPos - leftPos; 
    if (len < 2) 
     return; 
    if (len == 2) 
    { 
     if (arr[leftPos] > arr[leftPos + 1]) 
     { 
      var t = arr[leftPos]; 
      arr[leftPos] = arr[leftPos + 1]; 
      arr[leftPos + 1] = t; 
     } 
     return; 
    } 
    var rStart = leftPos+len/2; 
    var t1 = new Thread(delegate() { Sort(arr, leftPos, rStart, tempArr); }); 
    var t2 = new Thread(delegate() { Sort(arr, rStart, rightPos, tempArr); }); 
    t1.Start(); 
    t2.Start(); 
    t1.Join(); 
    t2.Join(); 
    var l = leftPos; 
    var r = rStart; 
    var z = leftPos; 
    while (l<rStart && r<rightPos) 
    { 
     if (arr[l] < arr[r]) 
     { 
      tempArr[z] = arr[l]; 
      l++; 
     } 
     else 
     { 
      tempArr[z] = arr[r]; 
      r++; 
     } 
     z++; 
    } 
    if (l < rStart) 
     Array.Copy(arr, l, tempArr, z, rStart - l); 
    else 
     Array.Copy(arr, r, tempArr, z, rightPos - r); 
    Array.Copy(tempArr, leftPos, arr, leftPos, rightPos - leftPos); 
} 

Answer 1

작업 병렬 라이브러리를 사용하면 스레드와 깨끗한 코드를보다 잘 추상화 할 수 있습니다. 아래 예제는 이것을 사용합니다.

코드와의 주요 차이점은 TPL을 사용하는 것 외에도 시작된 스레드 수에 관계없이 순차 구현이 사용되는 차단 임계 값보다 낮은 것입니다. 이렇게하면 매우 적은 양의 작업을 수행하는 스레드가 생성되지 않습니다. 또한 새 스레드가 만들어지지 않는 깊이 컷오프가 있습니다. 이렇게하면 사용 가능한 논리 코어 수 (Environment.ProcessCount)에 따라 하드웨어가 처리 할 수있는 것보다 더 많은 스레드가 생성되지 않습니다.

큰 배열의 스레드 폭발을 방지하고 작은 배열 크기의 경우에도 작업량이 매우 적은 스레드 생성을 방지하기 위해 이러한 두 가지 방법을 코드에 구현하는 것이 좋습니다. 또한 더 나은 성능을 제공합니다.

public static class Sort 
{ 
    public static int Threshold = 150; 

    public static void InsertionSort(int[] array, int from, int to) 
    { 
     // ... 
    } 

    static void Swap(int[] array, int i, int j) 
    { 
     // ... 
    } 

    static int Partition(int[] array, int from, int to, int pivot) 
    { 
     // ... 
    } 

    public static void ParallelQuickSort(int[] array) 
    { 
     ParallelQuickSort(array, 0, array.Length, 
      (int) Math.Log(Environment.ProcessorCount, 2) + 4); 
    } 

    static void ParallelQuickSort(int[] array, int from, int to, int depthRemaining) 
    { 
     if (to - from <= Threshold) 
     { 
      InsertionSort(array, from, to); 
     } 
     else 
     { 
      int pivot = from + (to - from)/2; // could be anything, use middle 
      pivot = Partition(array, from, to, pivot); 
      if (depthRemaining > 0) 
      { 
       Parallel.Invoke(
        () => ParallelQuickSort(array, from, pivot, depthRemaining - 1), 
        () => ParallelQuickSort(array, pivot + 1, to, depthRemaining - 1)); 
      } 
      else 
      { 
       ParallelQuickSort(array, from, pivot, 0); 
       ParallelQuickSort(array, pivot + 1, to, 0); 
      } 
     } 
    } 
} 

전체 소스는 당신이 당신의 논리를 잘 보인다 http://msdn.microsoft.com/en-us/library/ff963551.aspx