왜 목록 <>입니다. OrderBy LINQ는 IComparable + List <>보다 빠릅니다. 디버그 모드에서 정렬 하시겠습니까?

Question

LINQ를 사용하여 클래스를 정렬하거나 IComparable 인터페이스와 List.Sort를 구현하여 클래스를 정렬하는 것이 더 빠를 것인지 관심이있었습니다. LINQ 코드가 빨라 졌을 때 나는 놀랐다.

테스트를 수행하기 위해 필자는 그리 쉽지 않은 TestSort 이름으로 IComparable을 구현하는 아주 간단한 클래스를 만들었습니다.

class TestSort: IComparable<TestSort> { 
    private int age; 
    private string givenName; 

    public int Age { 
     get { 
      return age; 
     } 
     set { 
      age = value; 
     } 
    } 

    public string GivenName { 
     get { 
      return givenName; 
     } 
     set { 
      givenName = value; 
     } 
    } 

    public TestSort(int age, string name) { 
     this.age = age; 
     this.givenName = name; 
    } 

    public int CompareTo(TestSort other) { 
     return this.age.CompareTo(other.age); 
    } 
} 

다음에 여러 번 정렬하는 간단한 프로그램이 있습니다. 정렬은 목록을 복사하는 것보다 훨씬 비싸므로 그 효과는 무시할 수 있습니다.

class Program { 
    static void Main(string[] args) { 
     // Create the test data 
     string name = "Mr. Bob"; 

     Random r = new Random(); 
     var ts2 = new List<TestSort>(); 

     for (int i = 0; i < 100; i++) { 
      ts2.Add(new TestSort(r.Next(), name)); 
     } 

     DateTime start, end; 

     // Test List<>.Sort 
     start = DateTime.Now; 
     for (int i = 0; i < 100000; i++) { 
      var l = ts2.ToList(); 
      l.Sort(); 
     } 
     end = DateTime.Now; 

     Console.WriteLine("IComparable<T>: "); 
     Console.WriteLine((end - start).TotalMilliseconds); 


     // Test Linq OrderBy 
     start = DateTime.Now; 
     for (int i = 0; i < 100000; i++) { 
      var l = ts2.ToList(); 
      l = l.OrderBy(item => item.Age).ToList(); 
     } 
     end = DateTime.Now; 

     Console.WriteLine("\nLINQ: "); 
     Console.WriteLine((end - start).TotalMilliseconds); 

     Console.WriteLine("Finished."); 
     Console.ReadKey(); 
    } 
} 

나는 다음과 같은 출력이 나타납니다 아주 놀랐습니다 :

IComparable<T>: 
2965.1696 

LINQ: 
2181.1248 

때때로 LINQ 2000 아래로 갈 것이다, 나는 정상에 그것을 시험 할 때 때때로에서 IComparable은 약 3000

을 갈 것 List<Int>List.Sort은 LINQ의 1/4 속도로 약 2000에 머물렀다.

왜 LINQ가 ab 수업 시간에 평상시와 비교하면 66 % 나 빠릅니까? IComparable 구현에 문제가 있습니까?

업데이트 : 난 그냥 릴리스 모드에서 그 일을하려고 생각하고 예, 결과는 달랐다 :

IComparable<T>: 
1593.0911 

Linq: 
1958.1119 

하지만 여전히에서 IComparable 디버그 모드에서 느린 이유를 알고 매우 관심 .

Answer 1

확실 모든 측정을 시작하기 전에, 당신은 다른 결과가 (나는 또한 시간을 측정하기 위해 Stopwatch 클래스를 사용하는 것이 좋습니다) 얻을 수 있습니다 JITed되어 있는지 확인하는 경우 : 위의 내용을 추가 한 후

var ll = ts2.ToList(); 
ll.Sort(); 
ll.OrderBy(item => item.Age).ToList(); 

을 내 측정에 따르면 (코드), IComparable 항상 (심지어 디버그) 더 빠릅니다.

Answer 2

컴파일시 릴리스 모드에서 실행될 때 인라인으로 바뀌는 CompareTo 메서드를 호출하는 오버 헤드가 될 수 있습니다.

Answer 3

정렬은 최악의 경우 n * n 복잡도를 갖는 최적화되지 않은 quicksort를 사용합니다. 나는 orderby가 무엇을 사용하는지 모르지만, array.sort과는 달리, 안정된 정렬이기 때문에 같은 방법을 사용하지 않는다는 것을 안다.

Answer 4

나를 위해 Linq를 IComparable과 함께 사용합니다 (이 방법이 가장 많이 또는 유일한 방법 일 때). 당신이 ... 예를 들어 비교하는 여러 방법이 있습니다 목록, 배열 등 CompareTo에서 또한

, 당신이 할 수 있습니다 :이 경우, 항목은이 TestSort: IComparable<TestSort>

var sorted = ll.OrderBy(item => item); // This automatically used age to compare, as it's defined in CompareTo 

ll 어떤을 IEnumerable 될 수있다

public int CompareTo(TestSort other) { 
     return this.age != other.age ? this.age.CompareTo(other.age) : this.dateOfBirth.CompareTo(other.dateOfBirth); 
    }