C＃排序和OrderBy比較

Question

我可以使用Sort或OrderBy對列表進行排序。哪一個更快？兩個工作都是相同的 算法？

List<Person> persons = new List<Person>(); 
persons.Add(new Person("P005", "Janson")); 
persons.Add(new Person("P002", "Aravind")); 
persons.Add(new Person("P007", "Kazhal")); 

1.

persons.Sort((p1,p2)=>string.Compare(p1.Name,p2.Name,true)); 

2.

var query = persons.OrderBy(n => n.Name, new NameComparer()); 

class NameComparer : IComparer<string> 
{ 
    public int Compare(string x,string y) 
    { 
     return string.Compare(x, y, true); 
    } 
} 

Answer 1

爲什麼不衡量它：

class Program 
{ 
    class NameComparer : IComparer<string> 
    { 
     public int Compare(string x, string y) 
     { 
      return string.Compare(x, y, true); 
     } 
    } 

    class Person 
    { 
     public Person(string id, string name) 
     { 
      Id = id; 
      Name = name; 
     } 
     public string Id { get; set; } 
     public string Name { get; set; } 
    } 

    static void Main() 
    { 
     List<Person> persons = new List<Person>(); 
     persons.Add(new Person("P005", "Janson")); 
     persons.Add(new Person("P002", "Aravind")); 
     persons.Add(new Person("P007", "Kazhal")); 

     Sort(persons); 
     OrderBy(persons); 

     const int COUNT = 1000000; 
     Stopwatch watch = Stopwatch.StartNew(); 
     for (int i = 0; i < COUNT; i++) 
     { 
      Sort(persons); 
     } 
     watch.Stop(); 
     Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds); 

     watch = Stopwatch.StartNew(); 
     for (int i = 0; i < COUNT; i++) 
     { 
      OrderBy(persons); 
     } 
     watch.Stop(); 
     Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds); 
    } 

    static void Sort(List<Person> list) 
    { 
     list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true)); 
    } 

    static void OrderBy(List<Person> list) 
    { 
     var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray(); 
    } 
} 

在我的電腦在Release模式下編譯該程序打印時：

Sort: 1162ms 
OrderBy: 1269ms 

---

UPDATE：

正如所建議的@斯蒂芬在這裏是少數次排列大列表的結果：

List<Person> persons = new List<Person>(); 
for (int i = 0; i < 100000; i++) 
{ 
    persons.Add(new Person("P" + i.ToString(), "Janson" + i.ToString())); 
} 

Sort(persons); 
OrderBy(persons); 

const int COUNT = 30; 
Stopwatch watch = Stopwatch.StartNew(); 
for (int i = 0; i < COUNT; i++) 
{ 
    Sort(persons); 
} 
watch.Stop(); 
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds); 

watch = Stopwatch.StartNew(); 
for (int i = 0; i < COUNT; i++) 
{ 
    OrderBy(persons); 
} 
watch.Stop(); 
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds); 

打印：

Sort: 8965ms 
OrderBy: 8460ms 

在這種情況下，它看起來像排序依據執行得更好。

---

UPDATE2：

而且使用隨機的名字：

List<Person> persons = new List<Person>(); 
for (int i = 0; i < 100000; i++) 
{ 
    persons.Add(new Person("P" + i.ToString(), RandomString(5, true))); 
} 

其中：

private static Random randomSeed = new Random(); 
public static string RandomString(int size, bool lowerCase) 
{ 
    var sb = new StringBuilder(size); 
    int start = (lowerCase) ? 97 : 65; 
    for (int i = 0; i < size; i++) 
    { 
     sb.Append((char)(26 * randomSeed.NextDouble() + start)); 
    } 
    return sb.ToString(); 
} 

產量：

Sort: 8968ms 
OrderBy: 8728ms 

仍然排序依據是更快

Answer 2

不，他們是不一樣的算法。對於初學者，LINQ OrderBy被記錄爲穩定（即如果兩個項目具有相同的Name，他們將以其原始順序出現）。

它也取決於你是否緩衝查詢與迭代它幾次（LINQ到對象，除非你緩衝結果，將按照foreach重新排序）。

對於OrderBy查詢，我也非常想使用：

OrderBy(n => n.Name, StringComparer.{yourchoice}IgnoreCase); 

（爲{yourchoice}的CurrentCulture，Ordinal或InvariantCulture一個）。

List<T>.Sort

該方法使用的Array.Sort，其 使用快速排序算法。這個 執行執行不穩定的 排序;也就是說，如果兩個元素是 相等，則它們的順序可能不會被保存爲 。相反，穩定的分類 保留了 相等的元素的順序。

Enumerable.OrderBy

此方法執行一個穩定的排序;也就是說，如果兩個元素的鍵相等，則元素的順序被保留。相反，不穩定的排序不會保留具有相同鍵的元素的順序。 排序;也就是說，如果兩個元素是 相等，則它們的順序可能不會被保存爲 。相反，穩定的分類 保留了 相等的元素的順序。

Answer 3

我覺得要注意Sort和OrderBy的另一個區別是很重要的：

假設存在一個Person.CalculateSalary()方法，這需要大量的時間;甚至可能比排序大列表的操作還要多。

比較

// Option 1 
persons.Sort((p1, p2) => Compare(p1.CalculateSalary(), p2.CalculateSalary())); 
// Option 2 
var query = persons.OrderBy(p => p.CalculateSalary()); 

選項2可能具有優異的性能，因爲它僅調用CalculateSalary方法ñ倍，而Sort選項可能會調用CalculateSalary高達2n log(n)倍，這取決於排序算法的成功。

Answer 4

您應該計算OrderBy和Sort方法使用的算法的複雜度。 我記得QuickSort的複雜度爲n（log n），其中n是數組的長度。

我已經搜索了orderby's，但我甚至在msdn庫中都找不到任何信息。 如果你沒有任何相同的值和排序相關的只有一個屬性，我更喜歡使用 Sort（）方法;如果不是，則使用OrderBy。

Answer 5

Darin Dimitrov的回答顯示OrderBy在面對已排序的輸入時比List.Sort稍快。我修改了他的代碼，以便重複排序未排序的數據，並且在大多數情況下，它會稍微慢一些。

此外，OrderBy測試使用ToArray迫使LINQ的枚舉的枚舉，而是明顯地返回一個類型（Person[]），其是從所述輸入類型（List<Person>）不同。因此，我重新運行使用ToList而非ToArray的考驗，得到了一個更大的區別：

Sort: 25175ms 
OrderBy: 30259ms 
OrderByWithToList: 31458ms 

代碼：

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using System.Text; 

class Program 
{ 
    class NameComparer : IComparer<string> 
    { 
     public int Compare(string x, string y) 
     { 
      return string.Compare(x, y, true); 
     } 
    } 

    class Person 
    { 
     public Person(string id, string name) 
     { 
      Id = id; 
      Name = name; 
     } 
     public string Id { get; set; } 
     public string Name { get; set; } 
     public override string ToString() 
     { 
      return Id + ": " + Name; 
     } 
    } 

    private static Random randomSeed = new Random(); 
    public static string RandomString(int size, bool lowerCase) 
    { 
     var sb = new StringBuilder(size); 
     int start = (lowerCase) ? 97 : 65; 
     for (int i = 0; i < size; i++) 
     { 
      sb.Append((char)(26 * randomSeed.NextDouble() + start)); 
     } 
     return sb.ToString(); 
    } 

    private class PersonList : List<Person> 
    { 
     public PersonList(IEnumerable<Person> persons) 
      : base(persons) 
     { 
     } 

     public PersonList() 
     { 
     } 

     public override string ToString() 
     { 
      var names = Math.Min(Count, 5); 
      var builder = new StringBuilder(); 
      for (var i = 0; i < names; i++) 
       builder.Append(this[i]).Append(", "); 
      return builder.ToString(); 
     } 
    } 

    static void Main() 
    { 
     var persons = new PersonList(); 
     for (int i = 0; i < 100000; i++) 
     { 
      persons.Add(new Person("P" + i.ToString(), RandomString(5, true))); 
     } 

     var unsortedPersons = new PersonList(persons); 

     const int COUNT = 30; 
     Stopwatch watch = new Stopwatch(); 
     for (int i = 0; i < COUNT; i++) 
     { 
      watch.Start(); 
      Sort(persons); 
      watch.Stop(); 
      persons.Clear(); 
      persons.AddRange(unsortedPersons); 
     } 
     Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds); 

     watch = new Stopwatch(); 
     for (int i = 0; i < COUNT; i++) 
     { 
      watch.Start(); 
      OrderBy(persons); 
      watch.Stop(); 
      persons.Clear(); 
      persons.AddRange(unsortedPersons); 
     } 
     Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds); 

     watch = new Stopwatch(); 
     for (int i = 0; i < COUNT; i++) 
     { 
      watch.Start(); 
      OrderByWithToList(persons); 
      watch.Stop(); 
      persons.Clear(); 
      persons.AddRange(unsortedPersons); 
     } 
     Console.WriteLine("OrderByWithToList: {0}ms", watch.ElapsedMilliseconds); 
    } 

    static void Sort(List<Person> list) 
    { 
     list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true)); 
    } 

    static void OrderBy(List<Person> list) 
    { 
     var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray(); 
    } 

    static void OrderByWithToList(List<Person> list) 
    { 
     var result = list.OrderBy(n => n.Name, new NameComparer()).ToList(); 
    } 
}