Es wurde eine Frage zum Sortieren einer Liste gestellt. Es wurden mehrere Methoden von der Basis List.Sort () bis List.OrderBy () angegeben. Am lächerlichsten war ein SelectionSort-Roll-your-own. Ich habe das sofort abgelehnt, aber es hat mich zum Nachdenken gebracht; Würde nicht Linqs OrderBy (), auf eine Liste angewendet, dasselbe tun? myList.OrderBy (x = & gt; x.Property) .ToList () würde einen Iterator erzeugen, der im Grunde den Minimalwert der Projektion in dem, was von der Sammlung übrig ist, findet und die Ausbeute gibt sie zurück. Wenn man die gesamte Liste durchgeht, ist das eine Auswahlsortierung.
Was mich zum Nachdenken gebracht hat; Welche Algorithmen verwenden die integrierten Sortierer für Lists, SortedLists, Enumerables usw. und sollten sie auch für große Sammlungen vermieden werden? Eine SortedList würde, da sie nach Schlüsseln sortiert bleibt, wahrscheinlich bei jedem Hinzufügen einen Single-Pass-InsertionSort verwenden. finde den ersten Index mit einem Wert, der größer als der neue ist, und füge ihn davor ein. Listen und Arrays vereinheitlichen sich wahrscheinlich sehr effizient, aber ich kenne den eigentlichen Algorithmus hinter Sort () nicht. Wir haben über OrderBy gesprochen.
Was ich oben weiß, scheint darauf hinzuweisen, dass List.Sort () oder Array.Sort () die besten Optionen für eine Liste bekannter Größe sind, und die Verwendung von Linq zum Sortieren einer speicherinternen Liste oder eines Arrays sollte nicht empfohlen werden. Für einen Stream gibt es wirklich keinen anderen Weg als OrderBy () den Enumerable; Der Leistungsverlust wird durch die Tatsache gemildert, dass Sie die Daten als Stream speichern können, anstatt alles vor dem Sortieren zu haben.
BEARBEITEN:
Der allgemeine Konsens besteht darin, dass Sort () schneller ist, wenn eine Liste oder ein Array konkret implementiert wird. OrderBy ist sinnvoll, aber langsamer, da es O (N) -Komplexität beim Extrahieren eines Arrays aus dem übergebenen Enumerable hinzufügt. Die SortedList-Initialisierung endet mit O (N ^ 2), weil das unter der Haube ist. Moral der Geschichte, verwenden Sie List.Sort () anstelle von List.OrderBy (), wenn Sie eine tatsächliche Liste haben.
Enumerable.OrderBy () schlürft das IEnumerable & lt; & gt; in ein Array und verwendet schnelle Sortierung. O (n) Speicheranforderungen. Dies geschieht durch eine interne Klasse in System.Core.dll, EnumerableSort<TElement>.QuickSort() . Die Speicherkosten machen es nicht wettbewerbsfähig, einfach die Liste zu sortieren, wenn Sie eine haben, da List & lt; & gt; sortiert direkt an Ort und Stelle. Linq optimiert oft, indem er die wahren Fähigkeiten des IEnumerable mit dem is-Operator überprüft. Funktioniert hier nicht, da List & lt; & gt; .Sort destruktiv ist.
List & lt; & gt; .Sort und Array.Sort verwenden direktes schnelles Sortieren.
SortedList & lt; & gt; hat O (n) -Komplexität für eine Insertion und dominiert die O (log (n)) -Komplexität des Findens des Einfügepunkts. Wenn wir also N unsortierte Gegenstände hineinlegen, kostet das O (n ^ 2). SortedDictionary & lt; & gt; verwendet einen Rot-Schwarz-Baum, der die Komplexität von Einfügung O (log (n)) angibt. Also O (nlog (n)), um es zu füllen, gleich wie amortisierte schnelle Sortierung.
Ein kurzer Blick durch den Reflektor sagt mir, dass die List-Sort-Methoden den Quicksort Ссылка durch System.Collections.Generic.GenericArraySortHelper SortedList verwendet Array.BinarySearch, um herauszufinden, wo auf jedem Add Aufzählungen haben keine Sortierlogik Quicksort ist eine gute Sortieroption für die meisten Situationen, obwohl es sich O (n ^ 2) nähern kann, wenn Sie wirklich Pech mit den Eingabedaten haben. Wenn Sie vermuten, dass Ihre Eingabedaten ein riesiger Datenstapel in einer unglücklichen (bereits sortierten) Reihenfolge für Quicksort sind, besteht ein Trick darin, die Daten zuerst zu randomisieren (was immer billig ist) und dann zu tun die Sortierung nach den randomisierten Daten. Es gibt ein paar Tricks, die der Quicksort-Algorithmus implementieren kann, um das Problem des Sortierens von bereits sortierten (oder fast sortierten) Eingabedaten zu verringern. Ich weiß nicht, ob die BCL-Implementierung eines davon tut.
Eine Möglichkeit, die Leistung jeder Methode zu ermitteln, besteht darin, sie zu messen:
%Vor%Ergebnis:
Dies zeigt, dass die Leistung von OrderBy auch für sehr große Listen angemessen ist, aber es ist nicht ganz so schnell wie die Verwendung der integrierten Sort-Methode in einer Liste. Dies liegt wahrscheinlich daran, dass der Code für OrderBy etwas flexibler ist - er benötigt einen Schlüsselselektor, der für jedes Element ausgewertet werden muss.
Ja, Ihre Annahmen klingen richtig. Ich habe einen kleinen Test gemacht, um es zu bestätigen.
Bei 5000000 Ganzzahlen,
%Vor%Tags und Links .net performance sorting collections