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);
}
}
c#
.net
performance
sorting
sql-order-by
user215675
źródło
źródło
Odpowiedzi:
Dlaczego by tego nie zmierzyć:
Na moim komputerze po skompilowaniu w trybie wydania ten program drukuje:
AKTUALIZACJA:
Jak zasugerował @Stefan, oto wyniki sortowania dużej listy mniej razy:
Wydruki:
W tym scenariuszu wygląda na to, że OrderBy działa lepiej.
UPDATE2:
I używając losowych nazw:
Gdzie:
Plony:
Nadal OrderBy jest szybsze
źródło
LINQ
musi wydać dodatkową pamięć w porównaniu doList<T>.Sort
implementacji 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)Sort
osiąga lepsze wynikiOrderBy
we wszystkich przypadkach. Co więcej, patrząc naOrderedEnumerable<T>
kod źródłowy, wydaje się, że tworzy on trzy dodatkowe tablice (najpierw aBuffer<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.ToArray
wywoł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.Nie, to nie ten sam algorytm. Na początek LINQ
OrderBy
jest 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
OrderBy
zapytania również skusiłbym się na użycie:(dla
{yourchoice}
jednejCurrentCulture
,Ordinal
lubInvariantCulture
).List<T>.Sort
Enumerable.OrderBy
źródło
Enumerable.OrderBy
i przechodzenia do szczegółów jego wewnętrznej implementacji, możesz zobaczyć, że algorytm sortowania OrderBy jest wariantem QuickSort, który wykonuje stabilne sortowanie. (SEESystem.Linq.EnumerableSorter<TElement>
). W ten sposóbArray.Sort
iEnumerable.OrderBy
jak można się spodziewać, że O (N log n) czasy wykonania, gdzie N jest liczbą elementów zbioru.Odpowiedź Darina Dimitrova pokazuje, że
OrderBy
jest to nieco szybsze niż wList.Sort
przypadku 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
OrderBy
test używaToArray
do 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ącToList
zamiastToArray
i otrzymałem jeszcze większą różnicę:Kod:
źródło
OrderByWithToList
trwa to tyle samo coOrderBy
.Myślę, że ważne jest, aby zwrócić uwagę na inną różnicę między
Sort
aOrderBy
:Załóżmy, że istnieje
Person.CalculateSalary()
metoda, która zajmuje dużo czasu; prawdopodobnie więcej niż operacja sortowania dużej listy.Porównać
Opcja 2 może mieć lepszą wydajność, ponieważ wywołuje
CalculateSalary
metodę tylko n razy, podczas gdySort
opcja może wywołaćCalculateSalary
do 2 n razy log ( n ) , w zależności od sukcesu algorytmu sortowania.źródło
n
czasy CalculateSalary . Nie jest to oczywiście tak wygodne, jak korzystanie z OrderBy.W skrócie :
Sortowanie według listy / tablicy ():
OrderBy / ThenBy ():
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.
źródło
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.
źródło
Chcę tylko dodać, że orderby jest o wiele bardziej przydatny.
Czemu? Ponieważ mogę to zrobić:
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).
źródło