Сравнение сортировки и сортировки C # - PullRequest
Новая
       2

Сравнение сортировки и сортировки C #

93 голосов
/ 02 декабря 2009

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

Ответы [ 7 ]

115 голосов
/ 02 декабря 2009

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

Это также зависит от того, буферизуете ли вы запрос и повторяет его несколько раз (LINQ-to-Objects, если вы не буферизируете результат, будет переупорядочен в foreach).

Для запроса OrderBy я также хотел бы использовать: 

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

(для {yourchoice} один из CurrentCulture, Ordinal или InvariantCulture).

List<T>.Sort

Этот метод использует Array.Sort, который использует алгоритм быстрой сортировки. это реализация выполняет нестабильно Сортировать; то есть, если два элемента равны, их порядок не может быть сохранились. В отличие от стабильного рода сохраняет порядок элементов, которые равны.

Enumerable.OrderBy

Этот метод выполняет стабильную сортировку; то есть, если ключи двух элементов равны, порядок элементов сохраняется. Напротив, нестабильная сортировка не сохраняет порядок элементов, имеющих одинаковый ключ. Сортировать; то есть, если два элемента равны, их порядок не может быть сохранились. В отличие от стабильного рода сохраняет порядок элементов, которые равны.

86 голосов
/ 02 декабря 2009

Почему бы не измерить его: 

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:

Как подсказывает @Stefan, вот результаты сортировки большого списка меньше раз: 

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 быстрее

54 голосов
/ 06 февраля 2012

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

Кроме того, тест 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();
    }
}
35 голосов
/ 28 апреля 2010

Я думаю, что важно отметить еще одну разницу между 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 метод n раз, тогда как опция Sort может вызывать CalculateSalary до 2 n log ( n ) раз, в зависимости от успеха алгоритма сортировки.

9 голосов
/ 06 сентября 2018

В двух словах:

Список / Сортировка массива ():

  • Нестабильная сортировка.
  • Сделано на месте.
  • Используйте Introsort / Quicksort.
  • Пользовательское сравнение выполняется путем предоставления компаратора. Если сравнение стоит дорого, оно может быть медленнее, чем OrderBy () (что позволяет использовать ключи, см. Ниже).

OrderBy / ThenBy ():

  • Стабильная сортировка.
  • Не на месте.
  • Использование быстрой сортировки. Быстрая сортировка не является стабильной сортировкой. Вот хитрость: при сортировке, если два элемента имеют одинаковый ключ, сравнивается их начальный порядок (который был сохранен до сортировки).
  • Позволяет использовать ключи (используя лямбды) для сортировки элементов по их значениям (например: x => x.Id). Все ключи извлекаются в первую очередь перед сортировкой. Это может привести к лучшей производительности, чем использование Sort () и пользовательского компаратора.

Источники: MDSN , эталонный источник и dotnet / coreclr хранилище (GitHub).

Некоторые из приведенных выше утверждений основаны на текущей реализации платформы .NET (4.7.2). Это может измениться в будущем.

0 голосов
/ 19 марта 2018

Я просто хочу добавить, что порядок более полезен.

Почему?

Потому что я могу это сделать 

        Dim thisAccountBalances = account.DictOfBalances.Values.ToList
        thisAccountBalances.ForEach(Sub(x) x.computeBalanceOtherFactors())
        thisAccountBalances=thisAccountBalances.OrderBy(Function(x) x.TotalBalance).tolist
        listOfBalances.AddRange(thisAccountBalances)

Почему сложный компаратор? Просто сортировка по полю. Здесь я сортирую на основе TotalBalance.

Очень просто

Я не могу сделать это с помощью сортировки. Интересно, почему. Делайте хорошо с заказом.

Что касается скорости. Это всегда O (n)

0 голосов
/ 25 апреля 2011

Вы должны рассчитать сложность алгоритмов, используемых методами OrderBy и Sort. QuickSort имеет сложность n (log n), насколько я помню, где n - длина массива.

Я тоже искал Orderby's, но не смог найти никакой информации даже в библиотеке msdn. если у вас нет одинаковых значений и сортировки, связанных только с одним свойством, я предпочитаю использовать Метод сортировки (); если нет, то используйте OrderBy.

...