C# Sắp xếp và so sánh OrderBy

Question

Tôi có thể sắp xếp danh sách bằng cách sử dụng Sắp xếp hoặc OrderBy. Cái nào nhanh hơn? Cả hai đều đang làm việc trên cùng một thuật toán ?

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

Tại sao không đo lường nó:

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(); 
    } 
} 

Trên máy tính của tôi khi biên soạn trong chế độ Release chương trình này in:

Sort: 1162ms 
OrderBy: 1269ms 

---

UPDATE:

Theo đề nghị của @ Stefan ở đây là kết quả của việc sắp xếp một danh sách lớn ít lần hơn:

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); 

Prints:

Sort: 8965ms 
OrderBy: 8460ms 

Trong kịch bản này có vẻ như OrderBy thực hiện tốt hơn.

---

UPDATE2:

Và sử dụng tên ngẫu nhiên:

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

đâu:

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(); 
} 

Sản lượng:

Sort: 8968ms 
OrderBy: 8728ms 

Tuy OrderBy nhanh

Answer 2

Không, họ không phải là các thuật toán tương tự. Đối với người mới bắt đầu, LINQ OrderBy được ghi thành ổn định (tức là nếu hai mục có cùng số Name, chúng sẽ xuất hiện theo thứ tự ban đầu của chúng).

Nó cũng phụ thuộc vào việc bạn đệm truy vấn và lặp lại nó nhiều lần (LINQ-to-Objects, trừ khi bạn đệm kết quả, sẽ sắp xếp lại cho mỗi foreach).

Đối với truy vấn OrderBy, tôi cũng sẽ bị cám dỗ để sử dụng:

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

(cho {yourchoice} một trong CurrentCulture, Ordinal hoặc InvariantCulture).

List<T>.Sort

Phương pháp này sử dụng Array.Sort, mà sử dụng thuật toán Sắp xếp nhanh. Triển khai này thực hiện loại không an toàn ; tức là, nếu hai phần tử là bằng nhau, thứ tự của chúng có thể không được giữ nguyên là . Ngược lại, một loại ổn định giữ nguyên thứ tự của các phần tử mà bằng nhau.

Enumerable.OrderBy

Phương pháp này thực hiện một loại ổn định; nghĩa là, nếu các khóa của hai phần tử bằng nhau, thứ tự của các phần tử được giữ nguyên. Ngược lại, một loại không ổn định không bảo toàn thứ tự các phần tử có cùng khóa. sắp xếp; tức là, nếu hai phần tử là bằng nhau, thứ tự của chúng có thể không được giữ nguyên là . Ngược lại, một loại ổn định giữ nguyên thứ tự của các phần tử mà bằng nhau.

Answer 3

Tôi nghĩ rằng điều quan trọng cần lưu ý khác biệt nữa giữa Sort và OrderBy:

Giả sử có tồn tại một phương pháp Person.CalculateSalary(), trong đó có rất nhiều thời gian; có thể còn hơn cả hoạt động sắp xếp một danh sách lớn.

Hãy so sánh

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

Lựa chọn 2 có thể có hiệu suất cao, bởi vì nó chỉ gọi CalculateSalary phương pháp n lần, trong khi tùy chọn Sort có thể gọi CalculateSalary lên đến 2n log(n) lần, tùy thuộc vào thành công của thuật toán sắp xếp.

Answer 4

bạn nên tính toán độ phức tạp của thuật toán được sử dụng bởi các phương thức OrderBy và Sort. QuickSort có độ phức tạp của n (log n) như tôi nhớ, trong đó n là độ dài của mảng.

Tôi cũng đã tìm kiếm đơn đặt hàng, nhưng tôi không thể tìm thấy bất kỳ thông tin nào ngay cả trong thư viện msdn. nếu bạn không có bất kỳ giá trị giống nhau và phân loại liên quan đến chỉ một thuộc tính, tôi thích sử dụng phương pháp Sort(); nếu không sử dụng OrderBy.

Answer 5

Câu trả lời của Darin Dimitrov cho thấy rằng OrderBy hơi nhanh hơn List.Sort khi phải đối mặt với đầu vào đã được sắp xếp.Tôi đã sửa đổi mã của mình để mã này liên tục sắp xếp dữ liệu chưa được phân loại và OrderBy trong hầu hết các trường hợp hơi chậm.

Hơn nữa, kiểm tra OrderBy sử dụng ToArray để buộc đếm các Enumerator LINQ, nhưng đó rõ ràng là trả về một kiểu (Person[]) đó là khác biệt so với các loại đầu vào (List<Person>). Tôi do đó tái chạy thử nghiệm sử dụng ToList hơn ToArray và có một sự khác biệt lớn hơn:

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

Mã:

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(); 
    } 
}