Java und .NET: Warum werden standardmäßig unterschiedliche Sortieralgorithmen verwendet?

19

Ich frage mich nur warum Javaund .NET Frameworkverwende standardmäßig einen anderen Sortieralgorithmus.

In Java wird Array.Sort() standardmäßig der Merge Sort- Algorithmus verwendet, und wie auf Wikipedia.com angegeben :

In Java verwenden die Arrays.sort () -Methoden abhängig von den Datentypen eine Zusammenführungssortierung oder eine optimierte Schnellsortierung. Um die Implementierung effizienter zu gestalten, wechseln Sie zur Einfügungssortierung, wenn weniger als sieben Arrayelemente sortiert werden

In .NET Framework Array.Sort/List.Sort() verwendet Quick Sort als Standardsortieralgorithmus ( MSDN ):

List.Sort () 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 Elemente bei, die gleich sind.

Ein Blick auf die großartige Tabelle "Algorithmenvergleich" zeigt, dass sich beide Algorithmen in Bezug auf Worst Case und Memory Usage sehr unterschiedlich verhalten:

Bildbeschreibung hier eingeben

Sowohl Javaund .NETsind große Frameworks für Enterprise Solutions Entwicklung, sowohl hat Plattformen für Embedded - Entwicklung. Warum verwenden sie also standardmäßig andere Sortieralgorithmen?

sll
quelle
1
Weitere Informationen
yoozer8,

Antworten:

10

So deterministisch Computer auch sind, Computertechnik ist keine exakte Wissenschaft. Zwei Personen mit derselben Problemdomäne führen eine Analyse durch und entwickeln zwei verschiedene Lösungen, die alle Einschränkungen des Problems erfüllen. Es kann schwierig oder unmöglich sein, empirisch zu bestimmen, welches davon im allgemeinen Fall "besser" ist.

Ich vermute, dass .NET QuickSort über etwas in den MFCs oder der Windows-API gelegt ist und wahrscheinlich von viel älteren Windows-Versionen geerbt wurde, bei denen der Multi-Thread-Vorteil von MergeSort nicht einmal für die Computer von in Betracht gezogen worden wäre der Tag. ( BEARBEITEN: Dies ist nicht der Fall, obwohl Microsoft-Entwickler seit langer Zeit QuickSort-Fans sind, wie diese Wahl der Sortierimplementierung seit MS-DOS belegt.)

Java, das keine plattformspezifische Implementierung verwenden kann, weil Java von Grund auf plattformunabhängig entwickelt wurde, ist einen anderen Weg gegangen. Wer weiß, warum MergeSort die Nase vorn hat? Ich gehe davon aus, dass die Implementierung einen Leistungswettbewerb gegen andere von den Entwicklern entwickelte Varianten gewonnen hat, oder dass eine O (n) -space-MergeSort in Bezug auf Best-Case- und Worst-Case-Leistung auf dem Papier einfach am besten aussah (MergeSort hat keine Achillesferse in Bezug auf die Elementauswahl wie QuickSort, und der beste Fall ist eine nahezu sortierte Liste, während dies häufig die schlechteste von QuickSort ist.) Ich bezweifle, dass Multithreading-Vorteile ursprünglich in Betracht gezogen wurden, aber die derzeitige Implementierung kann durchaus Multithreading-Vorteile haben.

KeithS
quelle
1
List<T>.SortIn .NET wird eine systemeigene Methode verwendet, die in der CLR implementiert ist (wenn Sie keinen benutzerdefinierten Vergleicher verwenden), jedoch keine Abhängigkeiten von Betriebssystembibliotheken aufweist.
Joey
1
@Keith - .NET ist nicht auf irgendetwas aufgeschichtet und wurde plattformunabhängig entwickelt. Sie können die Implementierung hier sehen: github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/…
Robert MacLean
@RobertMacLean - ".NET wird nicht über alles gelegt" ist keine wahre Aussage, obwohl Sie gezeigt haben, dass die fragliche Sortierfunktion vollständig "verwalteter" Code ist. Große Teile von .NET, einschließlich Kryptografieunterstützung, Windows-Desktop-GUI-Bibliotheken und Windows-API-Interop (einschließlich Prozess- und Threading-Steuerung), basieren alle auf bereits vorhandenem nicht verwaltetem Code, einschließlich der MFCs. Sie müssen einfach sein; Windows selbst hat nur eine sehr kleine .NET-Komponente in seiner Codebasis, der Rest ist nicht verwaltet
KeithS
Microsoft-Entwickler sind nach wie vor bewährte Fans von QuickSort gegenüber anderen Implementierungen, da QuickSort seit MS-DOS der Algorithmus der Wahl ist, und dies hätte ihre Entscheidung beeinflusst, die .NET-Sortierung mit diesem Algorithmus zu implementieren.
KeithS
Diese Antwort ist so falsch, dass ich ehrlich schockiert bin.
user9993
17

Verschiedene Entwicklungsteams in zwei verschiedenen Unternehmen kamen zu unterschiedlichen Schlussfolgerungen hinsichtlich des üblichen Anwendungsfalls für ihre Frameworks und Komponenten und haben beschlossen, diese entsprechend zu implementieren.

Im Wesentlichen analysierte jedes Unternehmen seinen Kundenstamm und traf entsprechende Entscheidungen.

Es ist nicht zu erwarten, dass verschiedene Unternehmen und Teams Analysen durchführen und dabei unterschiedliche Annahmen und Rohdaten verwenden, um zu derselben Schlussfolgerung zu gelangen.

Oded
quelle
5
Oder auch die gleichen Annahmen und Rohdaten. . .
Wyatt Barnett
Ja, es war wahrscheinlich nur eine Gewohnheit - Microsoft war es gewohnt, die (instabile) Quicksort zu verwenden, Java wollte mit der Stable-Sorte gehen ... und Merge-Sorte war die schnellste bekannte Stable-Sorte ...
Rogerdpack
12

Diese Frage ist etwas veraltet, da Java jetzt Timsort verwendet (ab Java 7)

Von den genannten spezifischen Algorithmen:

  • Quicksort hat eine ungünstige Worst-Case-Leistung bei O (n ^ 2), ist jedoch etwas leichter und speicherintensiver, sodass im Normalfall eine bessere Leistung erzielt wird.

  • Mergesort hat bei O (n log n) die Worst-Case-Leistung garantiert, hat jedoch etwas mehr Overhead und Speicherbedarf. Es ist auch automatisch stabil (dh behält gleiche Elemente in der gleichen Reihenfolge bei).

Die Java-Designer scheinen im Allgemeinen etwas konservativer zu sein / sich auf das "Richtige" zu konzentrieren, daher ist es nicht verwunderlich, dass sie Mergesort aus den beiden ausgewählt haben, da es bessere Garantien bietet.

Sie sind sich nicht sicher, warum Microsoft sich für Quicksort entschieden hat, obwohl sie dadurch in einigen Micro-Benchmarks besser aussehen würden?

mikera
quelle