C # Sortowanie i porządkowanie według porównania

105

Mogę posortować listę za pomocą opcji Sortuj lub Sortuj według. Który jest szybszy? Czy oboje pracują na tym samym algorytmie?

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);
    }
}
user215675
źródło
22
Nie mogę uwierzyć, że żadna z odpowiedzi o tym nie wspomniała, ale największa różnica jest taka: OrderBy tworzy posortowaną kopię tablicy lub listy, podczas gdy Sort faktycznie sortuje ją na miejscu.
PRMan
2
jak tytuł mówi porównanie, chciałbym dodać, że OrderBy jest stabilny, a sortowanie stabilne do 16 elementów, ponieważ do 16 elementów sortowanie przez wstawianie jest używane, jeśli elementów jest więcej, wtedy przełącza się na inne niestabilne algorytmy Edycja: stabilna oznacza utrzymanie względnej kolejności elementów mających ten sam klucz.
Eklavyaa
@PRMan Nie, OrderBy tworzy leniwe wyliczalne. Tylko wtedy, gdy wywołasz metodę, taką jak ToList na zwróconym wyliczalnym, otrzymasz posortowaną kopię.
Stewart
1
@Stewart, Nie uważasz, że Array.Copy lub Collection.Copy do TElement [] w buforze w System.Core / System / Linq / Enumerable.cs za kopię? A jeśli wywołasz ToList w IEnumerable, możesz na chwilę mieć w pamięci 3 kopie naraz. Jest to problem w przypadku bardzo dużych tablic, o którym mówiłem. Ponadto, jeśli potrzebujesz tej samej kolejności posortowanej więcej niż raz, to jednokrotne wywołanie Sortuj na miejscu jest znacznie bardziej wydajne niż wielokrotne sortowanie listy, ze względu na jej trwałość.
PRMan
1
@PRMan Och, miałeś na myśli, że posortowana kopia jest zbudowana wewnętrznie. Nadal jest to niedokładne, ponieważ OrderBy nie tworzy kopii - z tego, co widzę, robi to metoda GetEnumerator, gdy faktycznie zaczynasz przeglądać kolekcję. Właśnie próbowałem przejść przez mój kod i stwierdziłem, że kod wypełniający zmienną z wyrażenia LINQ działa prawie natychmiast, ale kiedy przejdziesz do pętli foreach, spędza czas na sortowaniu. Myślę, że kiedy mam trochę więcej czasu, powinienem poświęcić trochę czasu na zastanowienie się, jak to działa za kulisami.
Stewart

Odpowiedzi:

90

Dlaczego by tego nie zmierzyć:

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

Na moim komputerze po skompilowaniu w trybie wydania ten program drukuje:

Sort: 1162ms
OrderBy: 1269ms

AKTUALIZACJA:

Jak zasugerował @Stefan, oto wyniki sortowania dużej listy mniej razy:

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

Wydruki:

Sort: 8965ms
OrderBy: 8460ms

W tym scenariuszu wygląda na to, że OrderBy działa lepiej.


UPDATE2:

I używając losowych nazw:

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

Gdzie:

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

Plony:

Sort: 8968ms
OrderBy: 8728ms

Nadal OrderBy jest szybsze

Darin Dimitrov
źródło
2
Myślę, że bardzo różni się sortowanie bardzo małej listy (3 pozycje) 1000000 razy lub sortowanie bardzo dużej listy (1000000 pozycji) tylko kilka razy. Oba są bardzo istotne. W praktyce najbardziej interesująca jest lista średniej wielkości (jaka jest średnia? ... powiedzmy na razie 1000 pozycji). IMHO, sortowanie list z 3 pozycjami nie ma większego znaczenia.
Stefan Steinegger
25
Zwróć uwagę, że istnieje różnica między „szybszym” a „zauważalnie szybszym”. W twoim ostatnim przykładzie różnica wynosiła około jednej czwartej sekundy. Czy użytkownik to zauważy? Czy niedopuszczalne jest, aby użytkownik czekał prawie dziewięć sekund na wynik? Jeśli odpowiedzi na oba pytania brzmią „nie”, to naprawdę nie ma znaczenia, które z nich wybierzesz z punktu widzenia wydajności.
Eric Lippert
12
Zwróć również uwagę, że test tutaj sortuje listę przed uruchomieniem stopera, więc porównujemy porównanie obu algorytmów w obliczu posortowanych danych wejściowych. Może to być zupełnie inne niż ich względne działanie z niesortowanymi danymi wejściowymi.
phoog
3
Wyniki te są dość zaskakujące dla IMHO, biorąc pod uwagę fakt, że LINQmusi wydać dodatkową pamięć w porównaniu do List<T>.Sortimplementacji w miejscu . Nie jestem pewien, czy ulepszyli to w nowszych wersjach .NET, ale na moim komputerze (i7 3.generacji 64-bitowa wersja .NET 4.5) Sortosiąga lepsze wyniki OrderBywe wszystkich przypadkach. Co więcej, patrząc na OrderedEnumerable<T>kod źródłowy, wydaje się, że tworzy on trzy dodatkowe tablice (najpierw a Buffer<T>, następnie tablicę rzutowanych kluczy, a następnie tablicę indeksów), po czym w końcu wywołuje Quicksort, aby posortować tablicę indeksów w miejscu.
Groo
2
... a po tym wszystkim następuje ToArraywywołanie, które tworzy wynikową tablicę. Operacje na pamięci i indeksowanie tablic to niezwykle szybkie operacje, ale nadal nie mogę znaleźć logiki stojącej za tymi wynikami.
Groo
121

Nie, to nie ten sam algorytm. Na początek LINQ OrderByjest dokumentowany jako stabilny (tj. Jeśli dwa elementy mają takie sameName , pojawią się w oryginalnej kolejności).

Zależy to również od tego, czy buforujesz zapytanie, czy wykonujesz je kilka razy (LINQ-to-Objects, chyba że zbuforujesz wynik, ponownie uporządkuje foreach ).

Do OrderByzapytania również skusiłbym się na użycie:

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

(dla {yourchoice}jednej CurrentCulture, Ordinallub InvariantCulture).

List<T>.Sort

Ta metoda używa Array.Sort, który używa algorytmu QuickSort. Ta implementacja wykonuje niestabilne sortowanie; to znaczy, jeśli dwa elementy są równe, ich kolejność może nie zostać zachowana. W przeciwieństwie do stabilnego sortowania zachowuje kolejność elementów, które są równe.

Enumerable.OrderBy

Ta metoda wykonuje stabilne sortowanie; to znaczy, jeśli klucze dwóch elementów są równe, kolejność elementów zostaje zachowana. Natomiast niestabilne sortowanie nie zachowuje kolejności elementów, które mają ten sam klucz. sortować; to znaczy, jeśli dwa elementy są równe, ich kolejność może nie zostać zachowana. W przeciwieństwie do stabilnego sortowania zachowuje kolejność elementów, które są równe.

Marc Gravell
źródło
5
Jeśli używasz .NET Reflector lub ILSpy do otwierania Enumerable.OrderByi przechodzenia do szczegółów jego wewnętrznej implementacji, możesz zobaczyć, że algorytm sortowania OrderBy jest wariantem QuickSort, który wykonuje stabilne sortowanie. (SEE System.Linq.EnumerableSorter<TElement>). W ten sposób Array.Sorti Enumerable.OrderByjak można się spodziewać, że O (N log n) czasy wykonania, gdzie N jest liczbą elementów zbioru.
John Beyer
@Marc Nie bardzo rozumiem, jaka byłaby różnica, gdyby dwa elementy były równe, a ich kolejność nie została zachowana. Z pewnością nie wygląda to na problem dla prymitywnych typów danych. Ale nawet dla typu referencyjnego, dlaczego miałoby to znaczenie, gdybym miał posortować, osoba o imieniu Marc Gravell pojawiła się przed inną osobą o imieniu Marc Gravell (na przykład :))? Nie kwestionuję Twojej odpowiedzi / wiedzy, raczej szukam zastosowania tego scenariusza.
Mukus
4
@Mukus wyobraź sobie, że sortujesz firmową książkę adresową według nazwy (a nawet daty urodzenia) - nieuchronnie pojawią się duplikaty. Ostatecznie pytanie brzmi: co się z nimi stanie? Czy zdefiniowano zamówienie podrzędne?
Marc Gravell
55

Odpowiedź Darina Dimitrova pokazuje, że OrderByjest to nieco szybsze niż w List.Sortprzypadku już posortowanych danych wejściowych. Zmodyfikowałem jego kod, aby wielokrotnie sortował nieposortowane dane iOrderBy jest w większości przypadków nieco wolniejszy.

Ponadto OrderBytest używa ToArraydo wymuszenia wyliczenia modułu wyliczającego Linq, ale to oczywiście zwraca typ ( Person[]), który różni się od input type ( List<Person>). Dlatego ponownie przeprowadziłem test, używając ToListzamiast ToArrayi otrzymałem jeszcze większą różnicę:

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

Kod:

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();
    }
}
phoog
źródło
2
Uruchamiam kod testowy teraz w LinqPad 5 (.net 5) i OrderByWithToListtrwa to tyle samo co OrderBy.
dovid
38

Myślę, że ważne jest, aby zwrócić uwagę na inną różnicę między Sorta OrderBy:

Załóżmy, że istnieje Person.CalculateSalary()metoda, która zajmuje dużo czasu; prawdopodobnie więcej niż operacja sortowania dużej listy.

Porównać

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

Opcja 2 może mieć lepszą wydajność, ponieważ wywołuje CalculateSalarymetodę tylko n razy, podczas gdy Sortopcja może wywołać CalculateSalarydo 2 n razy log ( n ) , w zależności od sukcesu algorytmu sortowania.

Omer Raviv
źródło
4
To prawda, chociaż istnieje rozwiązanie tego problemu, a mianowicie przechowywanie danych w tablicy i używanie przeciążenia Array.Sort, które pobiera dwie tablice, jedną z kluczy, a drugą z wartościami. Wypełniając tablicę kluczy, będziesz wywoływać nczasy CalculateSalary . Nie jest to oczywiście tak wygodne, jak korzystanie z OrderBy.
phoog
14

W skrócie :

Sortowanie według listy / tablicy ():

  • Niestabilny rodzaj.
  • Sporządzono na miejscu.
  • Użyj Introsort / Quicksort.
  • Niestandardowe porównanie odbywa się za pomocą modułu porównującego. Jeśli porównanie jest drogie, może być wolniejsze niż OrderBy () (które pozwalają na użycie kluczy, patrz poniżej).

OrderBy / ThenBy ():

  • Stabilny gatunek.
  • Nie na miejscu.
  • Użyj Quicksort. Quicksort nie jest typem stabilnym. Oto sztuczka: podczas sortowania, jeśli dwa elementy mają równy klucz, porównuje ich początkową kolejność (która została zapisana przed sortowaniem).
  • Pozwala na użycie kluczy (używając lambd) do sortowania elementów według ich wartości (np x => x.Id. :) . Wszystkie klucze są wyodrębniane jako pierwsze przed sortowaniem. Może to skutkować lepszą wydajnością niż użycie Sort () i niestandardowej funkcji porównującej.

Źródła: MDSN , źródło odniesienia i repozytorium dotnet / coreclr (GitHub).

Niektóre z powyższych stwierdzeń są oparte na aktualnej implementacji platformy .NET Framework (4.7.2). To może się zmienić w przyszłości.

tigrou
źródło
0

należy obliczyć złożoność algorytmów używanych przez metody OrderBy i Sort. Jak pamiętam, QuickSort ma złożoność n (log n), gdzie n jest długością tablicy.

Szukałem również orderby's, ale nie mogłem znaleźć żadnych informacji nawet w bibliotece msdn. jeśli nie masz żadnych takich samych wartości i sortowania związanego tylko z jedną właściwością, wolę użyć metody Sort (); jeśli nie, użyj OrderBy.

ikaptan
źródło
1
Zgodnie z aktualną dokumentacją MSDN Sort używa 3 różnych algorytmów sortowania na podstawie danych wejściowych. Wśród nich jest QuickSort. Pytanie o algorytm OrderBy () jest tutaj (Quicksort): stackoverflow.com/questions/2792074/…
Thor
-1

Chcę tylko dodać, że orderby jest o wiele bardziej przydatny.

Czemu? Ponieważ mogę to zrobić:

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

Dlaczego skomplikowana funkcja porównująca? Po prostu posortuj według pola. Tutaj sortuję na podstawie TotalBalance.

Bardzo łatwe.

Nie mogę tego zrobić z sortem. Zastanawiam się dlaczego. Zrób dobrze z orderBy.

Jeśli chodzi o prędkość, to zawsze jest O (n).

user4951
źródło
3
Pytanie: Czas O (n) (zakładam) w Twojej odpowiedzi odnosi się do OrderBy lub Comparer? Nie sądzę, aby szybkie sortowanie mogło osiągnąć czas O (N).
Kevman