Ich habe die Swift-Standardbibliotheksfunktion sort () für ihren Array-Typ ausgewählt und untersucht. Zu meiner Überraschung ist mir aufgefallen, dass es bei bereits sortierten Daten schlecht funktioniert. Das Sortieren eines Arrays von Ints, das gemischt ist, scheint 5x schneller zu sein als das Sortieren desselben Arrays, wenn es bereits sortiert ist. Das Sortieren eines Arrays aus gemischten Objekten ist etwa 4x schneller als das Sortieren des gleichen Objekts in sortierter Reihenfolge (Sortierung von Objekt-Array und int-Array verwenden unterschiedliche Algorithmen, ich bin mir sicher, dass ich beide sortiert habe, um Verzerrungen zu eliminieren). Dies sind die Ergebnisse:
%Vor%Als Referenz unten ist mein Code:
%Vor%}
Öffentliche Klasse CountedColor { public private (set) var Anzahl: Int public private (set) var Farbe: UIColor
%Vor%Meine Array shuffle () -Methode wurde aus diesem Post herausgezogen: Shuffle array swift 3 Mein ElapsedTimer wird einfach umbrochen und verwendet CACurrentMediaTime () - Funktionen.
Meine Frage ist, warum sehe ich dieses Verhalten? Vor allem, wenn ich das Objekt-Array sortiere, das sicher eine allgemeine Sorte verwenden sollte. Welche Art von Allzweck-Sortieralgorithmus wird schnell verwendet? Es kann sicherlich nicht einer sein, bei dem der Worst Case und der durchschnittliche Fall dieselben sind wie mergeSort.
Swift verwendet Introsort . Mit Blick auf den Quellcode sehen wir, dass der ausgewählte Pivot ist das erste Element. Die Wikipedia-Seite auf Introsort sagt:
(...), eine der kritischen Operationen ist die Auswahl des Pivot: Element, um das die Liste partitioniert ist. Der einfachste Drehpunkt Selektionsalgorithmus soll das erste oder das letzte Element des Liste als Pivot, verursacht ein schlechtes Verhalten für den Fall von sortierten oder fast sortierte Eingabe.
Somit ist es bei der Implementierung völlig vorhersehbar, dass Swifts Sortierleistung für sortierte Eingaben am schlechtesten ist.
Ich habe einen kompletten Benchmark für Leute erstellt, die die Behauptungen des OP einfach reproduzieren wollen: Ссылка
Als Referenz verwendet die GNU ISO C ++ - Standardbibliothek einen Median-von-3-Pivot (wie im Header stl_algo.h ).
Dies ist ein Duplikat dieser Frage: Implementierung des Swift-Sortieralgorithmus
>Außerdem ist der Grund, warum es beim Mischen so viel besser ist, wahrscheinlich nur darin zu sehen, dass seine Leistung nicht die obere Grenze von NlogN erreicht, wenn es gemischt ist. Das Sortieren des sortierten Arrays nähert sich wahrscheinlich diesem oberen Grenzwert, so dass es immer noch die gleiche Sortierung ist. Aber ich weiß nicht, das ist nur Theorie
Tags und Links arrays performance swift time-complexity sorting