C# Sort and OrderBy

Question

Я могу сортировать список, используя Сортировка или 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(); 
    } 
} 

На моем компьютере при компиляции в режиме выпуска программа печатает:

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 

В этом случае он выглядит как OrderBy работает лучше.

---

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 

Еще OrderBy быстрее

Answer 2

Нет, они не являются и тот же алгоритм. Для начала LINQ OrderBy документирован как стабильный (т. Е. Если два элемента имеют одинаковые Name, они будут отображаться в их первоначальном порядке).

Это также зависит от того, будет ли вы буферизовать запрос против итерации его несколько раз (LINQ-to-Objects, если вы не забудете результат, будет переупорядочен за 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, но я не мог найти никакой информации даже в библиотеке msdn. , если у вас нет одинаковых значений и сортировки, связанных только с одним свойством, я предпочитаю использовать метод Sort(); если не использовать OrderBy.

Answer 5

Ответ Дарина Димитрова показывает, что OrderBy немного быстрее, чем List.Sort, когда сталкивается с уже отсортированным входом.Я изменил его код, чтобы он неоднократно сортировал несортированные данные, а OrderBy в большинстве случаев немного медленнее.

Кроме того, тест использует OrderByToArray, чтобы заставить перечисление счетчику 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(); 
    } 
}