왜 C# quicksort 구현이 List <T>보다 상당히 느립니다 .Sort

Question

저는 C#에서 quicksort 버전을 구현했으며 C# List<T>.Sort과 비교하기 위해 빠른 벤치 마크를 수행했습니다. 내 구현이 라이브러리 버전보다 상당히 느리다는 것을 알았습니다. 이유를 이해하려고합니다. 다음은 대략적인 벤치 마크 번호입니다. 입력의 경우 중복 요소가 거의없이 무작위로 (균일 한) 생성 된 정수 목록을 사용했습니다. 모든 벤치 마크 시간은 평균 실행 횟수가입니다.

100,000 elements 
My code   0.096 seconds 
List<T>.Sort 0.011 seconds 

1,000,000 elements 
My code   1.10 seconds 
List<T>.Sort 0.14 seconds 

내 코드는 다음과 같습니다. 나는 10 % 향상 주위에 볼 인라인 내 Swap 및 ChoosePivotIndex 기능을 시도했습니다 -

• 가 인라인 : 여기에 내가 해봤 최적화 및 그 결과의 목록입니다.
• 피벗 선택 - 순진 피벗 선택 방법을 사용하고 있습니다. 난뿐만 아니라 세 무작위 요소의 중앙값을 사용하여 시도했다. 이것은 많은 개선을 가져 오지 않습니다. 벤치마킹에 사용하고있는 입력 데이터가 일정하게 무작위이기 때문에 이것이라고 생각합니다.
• 병렬 처리 - 재귀 적 분할 호출을 병렬로 시도했습니다. 이것은 실제로 실행 시간을 증가시키는 것 같습니다.
• 특수 케이스 작은 입력 - 작은 입력에 대한 삽입 정렬로 전환을 시도했습니다 (List<T>.Sort이 주장하는대로). 이는 약 20 %의 향상을 가져옵니다. 이러한 최적화의 조합으로

, 나는

100,000 elements - 0.062 seconds 
1,000,000 elements - 0.740 seconds 

이 여전히 라이브러리 정렬보다 훨씬 느립니다까지 내 코드를 얻을 수있었습니다. 성능 차이를 설명 할 수있는 코드가 있습니까? 아니면 작은 조정보다 나머지 70-80 %의 차이가 있습니까? .NET 프레임 워크는 정수, 문자열 정렬 방식 특별한 경우가 있기 때문에 코드가 아래

public class Quicksorter<T> where T : IComparable<T> 
{ 
    protected Random random; 
    public Quicksorter() 
    { 
     random = new Random(); 
    } 

    public void Sort(IList<T> items) 
    { 
     Partition(items, 0, items.Count-1); 
    } 

    private void Partition(IList<T> items, int startIndex, int endIndex) 
    { 
     if (startIndex >= endIndex) 
      return; 

     int pivotIndex = ChoosePivotIndex(items, startIndex, endIndex); 
     T pivot = items[pivotIndex]; 

     // swap pivot and first element 
     Swap(items, startIndex, pivotIndex); 

     int partitionIndex = startIndex + 1; 
     for (int frontierIndex = partitionIndex; frontierIndex <= endIndex; frontierIndex++) 
     { 
      if (items[frontierIndex].CompareTo(pivot) < 0) 
      { 
       Swap(items, frontierIndex, partitionIndex); 
       partitionIndex++; 
      } 
     } 
     // put pivot back 
     items[startIndex] = items[partitionIndex-1]; 
     items[partitionIndex - 1] = pivot; 

     // recursively sort left half 
     Partition(items, startIndex, partitionIndex - 2); 
     // recursively sort right half 
     Partition(items, partitionIndex, endIndex); 
    } 

    protected virtual int ChoosePivotIndex(IList<T> items, int startIndex, int endIndex) 
    { 
     return random.Next(startIndex, endIndex); 
    } 

    private void Swap(IList<T> items, int aIndex, int bIndex) 
    { 
     T temp = items[aIndex]; 
     items[aIndex] = items[bIndex]; 
     items[bIndex] = temp; 
    } 
} 

Answer 1

적인 버전 최적화되지 않은 내 기지 것을 참고, 및 기타 내장 유형. 비교를 위해 델리게이트를 호출하는 비용이 들지 않습니다. 내장 유형을 사용하여 정렬을 비교하는 경우 일반적으로 라이브러리 정렬이 훨씬 더 빠릅니다.