C # Sortieren und Bestellen durch Vergleich

105

Ich kann eine Liste mit Sortieren oder Bestellen sortieren. Welches ist schneller? Arbeiten beide an demselben Algorithmus?

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
quelle
22
Ich kann nicht glauben, dass keine der Antworten dies erwähnt hat, aber der größte Unterschied ist folgender: OrderBy erstellt eine sortierte Kopie des Arrays oder der Liste, während Sort sie tatsächlich sortiert.
PRMan
2
Als Titel sagen Vergleich, ich möchte hinzufügen, dass OrderBy stabil ist und Sortierung bis zu 16 Elemente stabil ist, da bis zu 16 Elemente Einfügungssortierung verwendet wird, wenn Elemente mehr als das sind, dann wechselt es zu anderen instabilen Algen. Bearbeiten: Stabil bedeutet, die relative Reihenfolge beizubehalten von Elementen mit demselben Schlüssel.
Eklavyaa
@PRMan Nein, OrderBy erstellt eine faule Aufzählung. Nur wenn Sie eine Methode wie ToList für die zurückgegebene Aufzählung aufrufen, erhalten Sie eine sortierte Kopie.
Stewart
1
@Stewart, Sie betrachten Array.Copy oder Collection.Copy in TElement [] im Puffer in System.Core / System / Linq / Enumerable.cs nicht als Kopie? Und wenn Sie ToList auf dem IEnumerable aufrufen, können Sie momentan 3 Kopien gleichzeitig im Speicher haben. Dies ist ein Problem für sehr große Arrays, was Teil meines Standpunkts war. Wenn Sie dieselbe sortierte Reihenfolge mehr als einmal benötigen, ist das Aufrufen von Sort an Ort und Stelle aufgrund ihrer Beständigkeit wesentlich effizienter als das wiederholte Sortieren der Liste.
PRMan
1
@PRMan Oh, Sie meinten, eine sortierte Kopie wird intern erstellt. Dies ist jedoch ungenau, da OrderBy die Kopie nicht erstellt. Soweit ich sehen kann, erfolgt dies mit der GetEnumerator-Methode, wenn Sie tatsächlich beginnen, die Sammlung zu durchlaufen. Ich habe gerade versucht, meinen Code durchzugehen, und festgestellt, dass der Code, der eine Variable aus einem LINQ-Ausdruck auffüllt, fast sofort ausgeführt wird. Wenn Sie jedoch in die foreach-Schleife wechseln, wird viel Zeit damit verbracht, sie zu sortieren. Ich denke, wenn ich etwas mehr Zeit habe, sollte ich versuchen herauszufinden, wie es hinter den Kulissen funktioniert.
Stewart

Antworten:

90

Warum nicht messen:

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

Auf meinem Computer druckt dieses Programm beim Kompilieren im Release-Modus:

Sort: 1162ms
OrderBy: 1269ms

AKTUALISIEREN:

Wie von @Stefan vorgeschlagen, sind hier die Ergebnisse der weniger häufigen Sortierung einer großen Liste:

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

Drucke:

Sort: 8965ms
OrderBy: 8460ms

In diesem Szenario sieht es so aus, als ob OrderBy eine bessere Leistung erbringt.


UPDATE2:

Und mit zufälligen Namen:

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

Wo:

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

Ausbeuten:

Sort: 8968ms
OrderBy: 8728ms

Trotzdem ist OrderBy schneller

Darin Dimitrov
quelle
2
Ich denke, es ist ganz anders, eine sehr kleine Liste (3 Elemente) 1000000 Mal zu sortieren oder eine sehr große Liste (1000000 Elemente) nur ein paar Mal zu sortieren. Beides ist sehr relevant. In der Praxis ist die mittlere Größe der Liste (was ist mittelgroß? ... sagen wir mal 1000 Elemente für den Moment) am interessantesten. IMHO ist das Sortieren von Listen mit 3 Elementen nicht sehr aussagekräftig.
Stefan Steinegger
25
Beachten Sie, dass es einen Unterschied zwischen "schneller" und "spürbar schneller" gibt. In Ihrem letzten Beispiel betrug der Unterschied etwa eine Viertelsekunde. Wird der Benutzer es bemerken? Ist es für den Benutzer nicht akzeptabel, fast neun Sekunden auf das Ergebnis zu warten? Wenn die Antworten auf beide Fragen "Nein" lauten, spielt es keine Rolle, welche Sie aus Sicht der Leistung auswählen.
Eric Lippert
12
Beachten Sie auch, dass der Test hier die Liste sortiert, bevor die Stoppuhr gestartet wird. Wir vergleichen also, wie sich die beiden Algorithmen vergleichen, wenn sie mit sortierten Eingaben konfrontiert werden. Dies kann sich erheblich von der relativen Leistung bei unsortierter Eingabe unterscheiden.
Phoog
3
Diese Ergebnisse sind meiner Meinung nach ziemlich überraschend, wenn man bedenkt, dass LINQim Vergleich zu einer direkten List<T>.SortImplementierung zusätzlicher Speicher benötigt wird . Ich bin nicht sicher, ob sie dies in neueren .NET-Versionen verbessert haben, aber auf meinem Computer (i7 3. Generation 64-Bit .NET 4.5-Version) Sortübertrifft es OrderByin allen Fällen. Wenn man sich den OrderedEnumerable<T>Quellcode ansieht , scheint es außerdem drei zusätzliche Arrays zu erstellen (zuerst a Buffer<T>, dann ein Array von projizierten Schlüsseln, dann ein Array von Indizes), bevor schließlich Quicksort aufgerufen wird, um das Array von Indizes an Ort und Stelle zu sortieren.
Groo
2
... und dann gibt es den ToArrayAufruf, der das resultierende Array erstellt. Speicheroperationen und Array-Indizierung sind unglaublich schnelle Operationen, aber ich kann die Logik hinter diesen Ergebnissen immer noch nicht finden.
Groo
121

Nein, sie sind nicht der gleiche Algorithmus. Für den Anfang wird der LINQ OrderByals stabil dokumentiert (dh wenn zwei Elemente dasselbe haben Name, werden sie in ihrer ursprünglichen Reihenfolge angezeigt).

Es hängt auch davon ab, ob Sie die Abfrage puffern oder mehrmals wiederholen (LINQ-to-Objects wird, sofern Sie das Ergebnis nicht puffern, nachbestellen foreach).

Für die OrderByAbfrage wäre ich auch versucht zu verwenden:

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

(für {yourchoice}einen von CurrentCulture, Ordinaloder InvariantCulture).

List<T>.Sort

Diese Methode verwendet Array.Sort, das den QuickSort-Algorithmus verwendet. Diese Implementierung führt eine instabile Sortierung durch. Das heißt, wenn zwei Elemente gleich sind, wird ihre Reihenfolge möglicherweise nicht beibehalten. Im Gegensatz dazu behält eine stabile Sortierung die Reihenfolge der gleichen Elemente bei.

Enumerable.OrderBy

Diese Methode führt eine stabile Sortierung durch. Das heißt, wenn die Schlüssel zweier Elemente gleich sind, bleibt die Reihenfolge der Elemente erhalten. Im Gegensatz dazu behält eine instabile Sortierung nicht die Reihenfolge der Elemente bei, die denselben Schlüssel haben. Sortieren; Das heißt, wenn zwei Elemente gleich sind, wird ihre Reihenfolge möglicherweise nicht beibehalten. Im Gegensatz dazu behält eine stabile Sortierung die Reihenfolge der gleichen Elemente bei.

Marc Gravell
quelle
5
Wenn Sie .NET Reflector oder ILSpy verwenden, um Enumerable.OrderBydie interne Implementierung zu öffnen und einen Drilldown durchzuführen, können Sie feststellen, dass der OrderBy-Sortieralgorithmus eine Variante von QuickSort ist, die eine stabile Sortierung durchführt. (Vgl System.Linq.EnumerableSorter<TElement>.) So , Array.Sortund Enumerable.OrderBykann sowohl zu erwarten haben O (N log N) Ausführungszeiten, wobei N die Anzahl der Elemente in der Sammlung ist.
John Beyer
@Marc Ich verfolge nicht ganz, was der Unterschied wäre, wenn zwei Elemente gleich wären und ihre Reihenfolge nicht beibehalten würde. Dies scheint für primitive Datentypen sicherlich kein Problem zu sein. Aber selbst für einen Referenztyp, warum sollte es wichtig sein, wenn ich sortieren würde, dass eine Person mit dem Namen Marc Gravell vor einer anderen Person mit dem Namen Marc Gravell erschien (zum Beispiel :))? Ich stelle Ihre Antwort / Ihr Wissen nicht in Frage, sondern suche nach einer Anwendung dieses Szenarios.
Mukus
4
@Mukus stellen Sie sich vor, Sie sortieren ein Firmenadressbuch nach Namen (oder tatsächlich nach Geburtsdatum) - es wird unvermeidlich Duplikate geben. Die Frage ist letztendlich: Was passiert mit ihnen? Ist die Unterreihenfolge definiert?
Marc Gravell
55

Die Antwort von Darin Dimitrov zeigt, dass dies OrderByetwas schneller ist als List.Sortbei bereits sortierten Eingaben. Ich habe seinen Code so geändert, dass er die unsortierten Daten wiederholt sortiert und OrderByin den meisten Fällen etwas langsamer ist.

Darüber hinaus wird beim OrderByTest die ToArrayAufzählung des Linq-Enumerators erzwungen, dies gibt jedoch offensichtlich einen Typ ( Person[]) zurück, der sich vom Eingabetyp ( List<Person>) unterscheidet. Ich habe den Test daher mit ToListund nicht wiederholt ToArrayund einen noch größeren Unterschied festgestellt :

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

Der Code:

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
quelle
2
Ich führe den Testcode jetzt in LinqPad 5 (.net 5) aus und das OrderByWithToListdauert genauso lange wie OrderBy.
Dovid
38

Ich denke, es ist wichtig, einen weiteren Unterschied zwischen Sortund festzustellen OrderBy:

Angenommen, es gibt eine Person.CalculateSalary()Methode, die viel Zeit in Anspruch nimmt. möglicherweise mehr als nur das Sortieren einer großen Liste.

Vergleichen Sie

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

Option 2 weist möglicherweise eine überlegene Leistung auf, da die CalculateSalaryMethode nur n- mal Sortaufgerufen wird , während die Option je nach Erfolg des Sortieralgorithmus CalculateSalarybis zu 2 n log ( n ) mal aufruft .

Omer Raviv
quelle
4
Dies ist wahr, obwohl es eine Lösung für dieses Problem gibt, nämlich die Daten in einem Array zu behalten und die Array.Sort-Überladung zu verwenden, die zwei Arrays benötigt, eines der Schlüssel und das andere der Werte. Wenn Sie das Schlüsselarray füllen, rufen Sie CalculateSalary ntimes auf. Dies ist offensichtlich nicht so bequem wie die Verwendung von OrderBy.
Phoog
14

In einer Nussschale :

List / Array Sort ():

  • Instabile Sortierung.
  • Fertig an Ort und Stelle.
  • Verwenden Sie Introsort / Quicksort.
  • Der benutzerdefinierte Vergleich erfolgt durch Bereitstellung eines Vergleichers. Wenn der Vergleich teuer ist, ist er möglicherweise langsamer als OrderBy () (mit dem Schlüssel verwendet werden können, siehe unten).

OrderBy / ThenBy ():

  • Stabile Sorte.
  • Nicht an Ort und Stelle.
  • Verwenden Sie Quicksort. Quicksort ist keine stabile Sorte. Hier ist der Trick: Wenn zwei Elemente beim Sortieren den gleichen Schlüssel haben, wird ihre ursprüngliche Reihenfolge verglichen (die vor dem Sortieren gespeichert wurde).
  • Ermöglicht die Verwendung von Schlüsseln (unter Verwendung von Lambdas), um Elemente nach ihren Werten zu sortieren (z x => x.Id. B. :) . Alle Schlüssel werden vor dem Sortieren zuerst extrahiert. Dies kann zu einer besseren Leistung führen als die Verwendung von Sort () und eines benutzerdefinierten Vergleichers.

Quellen: MDSN , Referenzquelle und Dotnet / Coreclr- Repository (GitHub).

Einige der oben aufgeführten Anweisungen basieren auf der aktuellen .NET Framework-Implementierung (4.7.2). Es könnte sich in Zukunft ändern.

Tigrou
quelle
0

Sie sollten die Komplexität der Algorithmen berechnen, die von den Methoden OrderBy und Sort verwendet werden. Wie ich mich erinnere, hat QuickSort eine Komplexität von n (log n), wobei n die Länge des Arrays ist.

Ich habe auch nach Orderby's gesucht, aber ich konnte selbst in der MSDN-Bibliothek keine Informationen finden. Wenn Sie nicht dieselben Werte und Sortierungen haben, die sich nur auf eine Eigenschaft beziehen, bevorzuge ich die Sort () -Methode. Wenn nicht, verwenden Sie OrderBy.

icaptan
quelle
1
Gemäß der aktuellen MSDN-Dokumentation verwendet Sort basierend auf der Eingabe 3 verschiedene Sortieralgorithmen. Darunter ist QuickSort. Frage zum OrderBy () Algorithmus ist hier (Quicksort): stackoverflow.com/questions/2792074/…
Thor
-1

Ich möchte nur hinzufügen, dass orderby viel nützlicher ist.

Warum? Weil ich das kann:

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

Warum komplizierter Vergleich? Sortieren Sie einfach nach einem Feld. Hier sortiere ich nach TotalBalance.

Sehr leicht.

Ich kann das nicht mit sort machen. Ich wundere mich warum. Machen Sie es gut mit orderBy.

Die Geschwindigkeit ist immer O (n).

user4951
quelle
3
Frage: Die O (n) -Zeit (ich nehme an) in Ihrer Antwort bezieht sich auf OrderBy oder Comparer? Ich glaube nicht, dass eine schnelle Sortierung eine O (N) -Zeit erreichen kann.
Kevman