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

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

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

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.

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

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.

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.

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.

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