爲什麼是List <>。OrderBy LINQ比IComparable + List <>更快。

我感興趣的是，使用LINQ對我的類進行排序，還是通過實現IComparable接口和List.Sort，會更快。當LINQ代碼更快時，我感到非常驚訝。爲什麼是List <>。OrderBy LINQ比IComparable + List <>更快。

爲了做這個測試，我做了一個非常簡單的類，使用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處於調試模式慢。

來源

2010-07-26 Vincent McNabb

你有沒有嘗試在調試模式（項目屬性）設置優化，看看它是否仍然較慢？如果沒有，那可能會解釋它。 – Gishu 2010-07-26 10:58:51

開啓優化代碼...我正在尋找一個真正的原因，而不是一個促成因素。我並沒有試圖解決這個問題，兩種方法對我而言都足夠快，我只想知道爲什麼。 – 2010-07-26 11:09:42

如果你把每件事情都JIT編譯的啓動措施之前，你可能會得到不同的結果（我也推薦使用Stopwatch類測量時間）：

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

根據我的測量（添加上述後代碼），IComparable總是更快（即使在調試中）。

來源

2010-07-26 12:50:42

在測量之前，您如何確保事物已被打亂？ – 2010-07-26 22:08:26

另外。在我的電腦上進行高達約900次的測試，IComparable速度更快。但是，如果我循環超過1000，那麼LINQ變得更快。所以在最初的LINQ設置上有一些開銷，但重複使用最終會變得更快。 – 2010-07-26 23:29:53

在代碼片段中，當您調用'll.OrderBy（）'時，列表已經在前一行進行了排序，所以調用OrderBy（）時可能發生的計算量較少。你能否在你的秒錶測試中驗證你是否在已經排序的列表上調用了'OrderBy（）'？ – devlord 2017-02-08 20:29:24

這可能是調用方法CompareTo的開銷，在編譯和在發佈模式下運行時，它將被內聯代替。

來源

2010-07-26 13:06:58 sgmoore

Sort使用未優化的快速排序，它在最壞的情況下具有n * n的複雜度。我不知道使用什麼orderby，但我知道它不使用相同的方法，因爲它是一個穩定的排序，不像array.sort。

來源

2011-12-06 12:59:26 Stajek

Linq到對象OrderBy使用穩定的快排，而Array.Sort使用不穩定的快排。算法的速度成本應該沒有太大的差別。它們都是O（n log n）。 – 2011-12-08 00:40:31

您是否知道它是否經過優化或者仍然存在相同的n^2最壞情況？ – Stajek 2012-03-30 16:25:37

對我來說，我將使用Linq與IComparable（當這是最簡單或唯一的排序方式）。在這種情況下，項目是TestSort: IComparable<TestSort>

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

ll可以是任何的IEnumerable：列表，陣列等

此外，在CompareTo你可以有多個方法來比較...例如，你可以做這樣的事情：

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

來源

2012-05-11 14:01:26 Jaider

爲什麼是List <>。OrderBy LINQ比IComparable + List <>更快。

回答

相關問題