C # Ordina e ordina per confronto

Posso ordinare una lista usando Sort o OrderBy. Qual è più veloce? Stanno entrambi lavorando sullo stesso algoritmo?

List persons = new List(); 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 { public int Compare(string x,string y) { return string.Compare(x, y, true); } } 

Perché non misurarlo:

 class Program { class NameComparer : IComparer { 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 persons = new List(); 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 list) { list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true)); } static void OrderBy(List list) { var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray(); } } 

Sul mio computer quando compilato in modalità Release questo programma stampa:

 Sort: 1162ms OrderBy: 1269ms 

AGGIORNARE:

Come suggerito da @Stefan, ecco i risultati dell’ordinamento di una grande lista un minor numero di volte:

 List persons = new List(); 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); 

stampe:

 Sort: 8965ms OrderBy: 8460ms 

In questo scenario sembra che OrderBy funzioni meglio.


UPDATE2:

E usando nomi casuali:

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

Dove:

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

I rendimenti:

 Sort: 8968ms OrderBy: 8728ms 

Still OrderBy è più veloce

No, non sono lo stesso algoritmo. Per i principianti, LINQ OrderBy è documentato come stabile (cioè se due articoli hanno lo stesso Name , appariranno nel loro ordine originale).

Dipende anche dal fatto che si bufferizzi la query o la si iteri in più volte (LINQ-to-Objects, a meno che non si bufferizzi il risultato, verrà riordinato per foreach ).

Per la query OrderBy , sarei tentato di utilizzare:

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

(per {yourchoice} uno di CurrentCulture , Ordinal o InvariantCulture ).

List.Sort

Questo metodo utilizza Array.Sort, che utilizza l’algoritmo QuickSort. Questa implementazione esegue un ordinamento instabile; cioè, se due elementi sono uguali, il loro ordine potrebbe non essere conservato. Al contrario, un ordinamento stabile conserva l’ordine degli elementi uguali.

Enumerable.OrderBy

Questo metodo esegue un ordinamento stabile; cioè, se le chiavi di due elementi sono uguali, l’ordine degli elementi viene mantenuto. Al contrario, un ordinamento instabile non conserva l’ordine degli elementi che hanno la stessa chiave. ordinare; cioè, se due elementi sono uguali, il loro ordine potrebbe non essere conservato. Al contrario, un ordinamento stabile conserva l’ordine degli elementi uguali.

La risposta di Darin Dimitrov mostra che OrderBy è leggermente più veloce di List.Sort quando si trova di fronte a input già ordinati. Ho modificato il suo codice in modo da ordinare ripetutamente i dati non ordinati e OrderBy nella maggior parte dei casi è leggermente più lento.

Inoltre, il test OrderBy utilizza ToArray per forzare l’enumerazione dell’enumeratore Linq, ma ovviamente restituisce un tipo ( Person[] ) diverso dal tipo di input ( List ). Quindi ho ripetuto il test usando ToList piuttosto che ToArray e ho ottenuto una differenza ancora più grande:

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

Il codice:

 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; class Program { class NameComparer : IComparer { 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 { public PersonList(IEnumerable 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 list) { list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true)); } static void OrderBy(List list) { var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray(); } static void OrderByWithToList(List list) { var result = list.OrderBy(n => n.Name, new NameComparer()).ToList(); } } 

Penso che sia importante notare un’altra differenza tra Sort e OrderBy :

Supponiamo che esista un metodo Person.CalculateSalary() , che richiede molto tempo; forse più che persino l’operazione di ordinare una grande lista.

Confrontare

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

L’opzione 2 potrebbe avere prestazioni superiori, poiché chiama il metodo CalculateSalary solo n volte, mentre l’opzione Sort potrebbe chiamare CalculateSalary fino a 2 n log ( n ) volte, a seconda del successo dell’algoritmo di ordinamento.

dovresti calcolare la complessità degli algoritmi utilizzati dai metodi OrderBy e Sort. QuickSort ha una complessità di n (log n) come ricordo, dove n è la lunghezza dell’array.

ho cercato anche per orderby, ma non sono riuscito a trovare alcuna informazione nemmeno nella libreria msdn. se non hai gli stessi valori e ordinamento relativi a una sola proprietà, preferisco usare il metodo Sort (); se non usare OrderBy.

Voglio solo aggiungere che orderby è molto più utile.

Perché?

Perché posso farlo

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

Perché comparatore complicato? Basta ordinare in base a un campo. Eccomi l’ordinamento basato su TotalBalance.

Molto facile

Non posso farlo con sorta. Mi chiedo perché. Fai bene con orderBy.

Per quanto riguarda la velocità. È sempre O (n)