C: Analyse der Sortiermethoden

sortperf.py hat eine gut ausgewählte Suite von Benchmark-Testfällen und wurde verwendet, um den Aufsatz hier zu unterstützen und zu machen timsort DIE Sortierung in Python vor vielen Jahren. Beachten Sie, dass Java dank Josh Block möglicherweise auch zu timsort wechselt (siehe hier ), also stelle ich mir vor, dass sie ihre eigene Version der Benchmark-Testfälle geschrieben haben - ich kann jedoch nicht leicht einen Verweis darauf finden. (timsort, eine stabile, adaptive, iterative natürliche Mergesort-Variante, eignet sich besonders für Sprachen mit Objekt-zu-Objekt-Semantiken wie Python und Java, wo "Datenbewegung" relativ billig ist [[da alles, was jemals bewegt wird, Referenzen als Zeiger sind , keine Blobs von unbegrenzter Größe ;-)]], aber Vergleiche können relativ kostspielig sein [[da es keine Obergrenze für die Komplexität einer Vergleichsfunktion gibt -, sondern dies gilt für jede Sprache, in der die Sortierung über eine benutzerdefinierte Methode angepasst werden kann Vergleich oder Schlüssel-Extraktionsfunktion]]).

Diese ausführliche Diskussion sowie die Verknüpfung mit einer großen Anzahl von verwandten Webseiten, die Sie wahrscheinlich finden werden nützlich, beschreibt auch einen nützlichen Satz von Eingabedaten zum Testen von Sortieralgorithmen (siehe die verlinkte Seite aus Gründen). Zusammenfassung:

1. Vollständig zufällig neu angeordnetes Array
2. Bereits sortiertes Array
3. Bereits in umgekehrter Reihenfolge sortiertes Array
4. Kettensägen-Array
5. Array identischer Elemente
6. Bereits sortiertes Array mit N Permutationen (mit N von 0,1 bis 10% der Größe)
7. Bereits sortiertes Array in umgekehrter Reihenfolge mit N Permutationen
8. Daten mit normaler Verteilung mit doppelten (oder geschlossenen) Schlüsseln (nur für stabile Sortierung)
9. Pseudozufallsdaten (tägliche Werte von S & amp; P500 oder anderer Index für ein Jahrzehnt könnten hier ein guter Test sein; sie sind von Yahoo.com erhältlich)

Die definitive Studie der Sortierung ist Bob Sedgewick Aber es gibt eine Menge guter Informationen in seinen Algorithmen-Lehrbüchern, und das sind die ersten beiden Stellen, an denen ich nach Testsuite und Methodik suchen würde. Wenn Sie einen kürzlichen Kurs hatten, werden Sie mehr wissen als ich; Letztes Mal, als ich einen Kurs hatte, war die beste Methode, Quicksort bis zu Partitionen der Größe 12 zu verwenden und dann Insertion sort für das gesamte Array auszuführen. Aber die Antworten ändern sich so schnell wie die Hardware.

Jon Bentley Programming Perls Bücher haben einige andere Informationen zum Sortieren.

Sie können schnell eine Testsuite mit

• Zufällige Ganzzahlen

• Sortierte Ganzzahlen

• Sortierte ganze Zahlen umkehren

• Sortierte ganze Zahlen, leicht gestört

Wenn Speicher dient, sind dies die wichtigsten Fälle für einen Sortieralgorithmus.

Wenn Sie nach Arrays suchen, die nicht in den Cache passen, müssen Sie Cache-Effekte messen. valgrind ist effektiv, wenn langsam.

Diese Seite zeigt die verschiedenen Sortieralgorithmen mit vier Gruppen: Ссылка

Zusätzlich zu den vier Gruppen in Normans Antwort möchten Sie die Sortieralgorithmen mit einer Sammlung von Zahlen überprüfen, die einige Ähnlichkeiten in den Zahlen aufweisen:

• Alle Ganzzahlen sind eindeutig
• Dieselbe Ganzzahl in der gesamten Sammlung
• Wenige eindeutige Schlüssel

Es ist auch eine gute Übung, die Anzahl der Elemente in der Sammlung zu ändern. Überprüfen Sie jeden Algorithmus mit 1K, 1M, 1G usw., um zu sehen, welche Auswirkungen dieser Algorithmus auf den Speicher hat.