Es scheint, dass es im Front-End-Kreis immer ein Missverständnis gegeben hat: Das Front-End kann Algorithmuswissen nicht verwenden. Möglicherweise wurde möglicherweise jeder von dieser Aussage beeinflusst. Bis ich vor einiger Zeit auf eine Produktnachfrage gestoßen bin, schaute ich zurück und stellte fest, dass dies nicht der Fall war.
Front-End-Sortierung
Front-End-Sortierszenario
Das Front-End überträgt die Sortierbedingung als Anforderungsparameter an das Back-End, und das Back-End gibt das Sortierergebnis als Anfrageantwort auf das Front-End zurück, was ein gemeinsames Design ist. Aber es ist nicht so geeignet für einige Produkte.
Stellen Sie sich ein Szenario vor: Wenn Sie eine Food -App verwenden, wechseln Sie häufig die Sortiermethode, sortieren Sie sie nach dem Preis und sortieren Sie sie dann durch Bewertung.
In der tatsächlichen Produktion wird aufgrund von Faktoren wie Serverkosten, wenn eine einzige Datenabfrage zu einem Gesamtbeteiligungspunkt wird, auch in Betracht gezogen, um die Leistung zu optimieren, indem sie im Front-End sortiert werden.
Sortieren von Algorithmus
Ich bin der Meinung, dass es nicht nötig ist, dies vorzustellen. Als Basisalgorithmus in der Informatik wird die Beschreibung direkt aus Wikipedia kopiert.
Dieser Absatz existiert hier nur, um den ersten (Mann) und den zweiten (shu) zu erben.
JavaScript -Sortierung
Da wir über Front-End-Sortierung sprechen, werden wir natürlich an JavaScripts native Schnittstelle Array.prototype.sort von JavaScript denken.
Diese Schnittstelle existiert seit ECMAScript 1st Edition . Mal sehen, wie die Beschreibung in der neuesten Spezifikation aussieht.
Array.Prototype.Sort -Spezifikation
Array.prototype.sort(compareFn)
Die Codekopie lautet wie folgt:
Die Elemente dieses Arrays sind sortiert. Die Art ist nicht notwendig stabil (dh Elemente, die gleich vergleichen, bleiben nicht unbedingt in ihrer ursprünglichen Reihenfolge). Wenn verglichen nicht und definiert ist, sollte es eine Funktion sein, die zwei Argumente x und y akzeptiert und einen negativen Wert zurückgibt, wenn x <y, Null, wenn x = y oder einen positiven Wert, wenn x> y.
Offensichtlich begrenzt die Spezifikation nicht, wie der sort -Algorithmus intern implementiert wird. Selbst die Implementierung der Schnittstelle muss nicht stabil sortiert sein. Dies ist sehr wichtig und wird als nächstes viele Male beteiligt sein.
In diesem Zusammenhang hängt die Front-End-Sortierung tatsächlich von der spezifischen Implementierung jedes Browsers ab. Wie implementieren Mainstream -Browser die Sortierung? Als nächstes vergleichen wir kurz Chrome , Firefox und Microsoft Edge .
Implementierung in Chrome
Chromes JavaScript -Engine ist V8. Da es sich um Open Source handelt, können Sie den Quellcode direkt betrachten.
Das gesamte Array.js wird in der JavaScript -Sprache implementiert. Der Teil der Sortiermethode ist offensichtlich viel komplizierter als die schnelle Sortierung, die ich gesehen habe, aber offensichtlich ist der Kernalgorithmus immer noch schnell sortiert. Der Grund für den komplexen Algorithmus ist, dass V8 viele Optimierungen für Leistungsüberlegungen vorgenommen hat. (Ich werde als nächstes darüber sprechen)
Implementierung in Firefox
Es ist nicht möglich zu bestimmen, was der Array -Sortieralgorithmus, den die JavaScript -Engine von Firefox verwendet, verwenden soll. [3]
Gemäß den vorhandenen Informationen implementiert Spidermoney -Implementierungen die Zusammenführung der Sortierung intern.
Implementierung in Microsoft Edge
Der Kernbestandteil des Codes für das JavaScript -Engine -Chakra von Microsoft Edge wurde Anfang 2016 auf Github eröffnet.
Wenn wir uns den Quellcode ansehen, können wir feststellen, dass Chakras Array -Sortieralgorithmus auch eine schnelle Sortierung implementiert. Und im Vergleich zu V8 implementiert es nur eine rein schnelle Sortierung, ohne dass überhaupt keine Leistungsoptimierungen in V8 sind.
Probleme mit der Sortierung von JavaScript -Array
Wie wir alle wissen, ist Schnellsortierung ein instabiler Sortieralgorithmus, während die Sortierung von Merge ein stabiler Sortieralgorithmus ist. Aufgrund der Unterschiede in der Algorithmusauswahl verschiedener Motoren beruht das Front-End auf dem vom Array.Prototype.Sort-Schnittstelle implementierten JavaScript-Code, und der tatsächliche Sortierungseffekt, der im Browser durchgeführt wird, ist inkonsistent.
Unterschiede in der Sortierstabilität müssen durch bestimmte Szenarien ausgelöst werden, bevor ein Problem vorliegt. In vielen Fällen hat eine instabile Sortierung keinen Einfluss.
Wenn bei der Sortierung von Arrays in der tatsächlichen Projektentwicklung keine Stabilität erforderlich ist, können Sie dies tatsächlich sehen, und die Implementierungsunterschiede zwischen Browsern sind nicht so wichtig.
Wenn das Projekt jedoch verlangt, dass die Art stabil sein muss, wird die Existenz dieser Unterschiede die Nachfrage nicht entsprechen. Wir müssen zusätzliche Arbeit dafür erledigen.
Zum Beispiel:
Die endgültigen Gewinnregeln für das Auktionssystem des Kraftfahrzeuglizenzes in einer bestimmten Stadt sind:
1. sortieren nach Preis umgekehrt;
2. Der gleiche Preis wird nach der Ausschreibungsauftrag (d. H. Die Preisübertragungszeit) positiv sortiert.
Wenn die Sortierung am vorderen Ende erfolgt, ist der Gewinner, der im Browser mit der Schnellsorte angezeigt wird, wahrscheinlich nicht mit den Erwartungen überein.
Erforschen Sie die Unterschiede
Bevor Sie eine Lösung finden, müssen die Gründe für das Problem untersucht werden.
Warum Chrome schnell sortiert
Tatsächlich existierte diese Situation von Anfang an.
Chrome Beta wurde am 2. September 2008 veröffentlicht. Kurz nach seiner Veröffentlichung reichten einige Entwickler jedoch #90 Feedback für die Chromiumentwicklungsgruppe ein. Die Implementierung von Array -Sortierungen von V8 ist nicht stabil.
Diese Diskussionsdiskussion in dieser Fehlerprobleme erstreckt sich viel. Bis zum 10. November 2015 kommentierten Entwickler immer noch die Implementierung der Array -Sortierung in V8.
Gleichzeitig haben wir auch festgestellt, dass das Problem geschlossen wurde. Es wurde jedoch im Juni 2013 von den Mitgliedern des Entwicklungsteams als Referenz für die Diskussion des nächsten Spezifikationen des ECMASScripts wiedereröffnet.
Und die endgültige Schlussfolgerung von ES-Discuss ist
Die Codekopie lautet wie folgt:
Es ändert sich nicht. Stabil ist eine Untergruppe von instabilen. Und umgekehrt gibt jeder instabile Algorithmus ein stabiles Ergebnis für einige Eingänge zurück. Marks Punkt ist, dass das Erfordernis „immer instabil“ keine Bedeutung hat, egal welche Sprache Sie wählen.
/Andreas
Wie in der bereits in diesem Artikel angeführten Spezifikation der ECMAScript 2015 beschrieben.
Eigenschaften der Zeit
IMHO, dieses Problem wurde zu Beginn von Chromes Veröffentlichung gemeldet, die möglicherweise ihre eigenen besonderen Eigenschaften der Zeit aufweist.
Wie oben erwähnt, wurde die erste Version von Chrome im September 2008 veröffentlicht. Laut Statistiken von StatCounter waren die beiden Browser mit dem höchsten Marktanteil in diesem Zeitraum IE (nur IE6 und IE7 zu diesem Zeitpunkt) und Firefox, wobei der Marktanteil 67,16% bzw. 25,77% erreichte. Mit anderen Worten, der kombinierte Marktanteil der beiden Browser übersteigt 90%.
Laut einem anderen Browser -Sortieralgorithmus -Statistik vermitteln diese beiden Browser mit mehr als 90% Marktanteil stabiler Array -Sortieren. Daher ist es vernünftig, von Entwicklern zu Beginn der Veröffentlichung von Chrom befragt zu werden.
Die Spezifikationen entsprechen
Aus der Diskussion des Fehlerproblems können wir einige Überlegungen der Entwicklungsteammitglieder bei der schnellen Sortierung der Motorimplementierung grob verstehen.
Eines davon ist, dass sie glauben, dass der Engine der ECMascript -Spezifikation einhalten muss. Da die Spezifikation keine Beschreibung der stabilen Sortierung erfordert, ist sie der Ansicht, dass die Implementierung von V8 vollständig mit der Spezifikation übereinstimmt.
Leistungsüberlegungen
Darüber hinaus sind sie der Ansicht, dass eine wichtige Überlegung beim V8 -Design die Leistung des Motors ist.
Schnellsortierung führt eine bessere Gesamtleistung als die Sortierung des Zusammenführungssortierens durch:
Höhere Recheneffizienz. Die schnelle Sortierung ist in einer tatsächlichen Computerausführungsumgebung schneller als andere Sortieralgorithmen mit der gleichen Zeitkomplexität (bei dem der schlimmste Kombination nicht aufzurufen)
Niedrigere Raumkosten. Ersteres hat nur O (n) Raumkomplexität im Vergleich zur letzteren O (N) -Spalienkomplexität ist der Speicherverbrauch während der Laufzeit geringer.
Leistungsoptimierung von V8 im Array -Sortieralgorithmus
Was macht es in der Array -Sortierung, da V8 sehr an Motorleistung interessiert ist?
Durch das Lesen des Quellcodes habe ich immer noch einige Grundkenntnisse gelernt.
Gemischte Sortierung
Schnelles Sortieren ist die Idee, große Arrays zu teilen und zu erobern und zu zersetzen und sie für Schicht nach unten zu überholen. Wenn die Rekursionstiefe jedoch zu groß ist, ist der Verbrauch des rekursiven Anrufstapels auch sehr groß. Eine schlechte Optimierung kann sogar einen Stapelüberlauf verursachen.
Die aktuelle Implementierung von V8 besteht darin, einen Schwellenwert einzustellen und Sortierung für kleine Arrays von 10 oder weniger Längen in der niedrigsten Schicht zu verwenden.
Nach Code -Kommentaren und -beschreibungen in Wikipedia ist die durchschnittliche Zeitkomplexität der Insertionssorte o (n²) schlechter als die von schneller Sortierung O (NN). In der laufenden Umgebung ist die Effizienz der Verwendung von Sortieren kleiner Arrays jedoch effizienter als die schnelle Sortierung, sodass es hier nicht erweitert wird.
Beispiel für V8 -Code
var quicksort = function QuickSort (a, von, bis) {...... while (true) {// Insertions -Sortierung für kurze Arrays schneller. if (zu - von <= 10) {Insertionsort (a, von, nach); zurückkehren; } ......} ......};Drei Zahlen sind in
Wie bekannt ist, ist die Schnellsortier -Achilles -Ferse, dass der Algorithmus in der schlimmsten Array -Kombination entartet wird.
Der Kern des Schnellsortieralgorithmus besteht darin, einen Drehpunkt auszuwählen und das Array zu zersetzen, das gemäß der Referenz für die nachfolgende Rekursion verglichen und in zwei Zahlenbereiche ausgetauscht wurde. Stellen Sie sich vor, für ein bereits bestelltes Array wird das erste oder letzte Element jedes Mal ausgewählt, wenn das Referenzelement ausgewählt wird, dann wird es jedes Mal eine Zahlenfläche geben, und die rekursive Anzahl von Schichten erreicht N, was schließlich zum Zeitkomplexität des Algorithmus zu O (n²) führt. Daher ist die Wahl des Drehausfalls sehr wichtig.
V8 verwendet die Optimierung von median-of-three : Zusätzlich zu den beiden Elementen zu Beginn und am Ende wird ein weiteres Element ausgewählt, um an der Konkurrenz des Benchmark-Elements teilzunehmen.
Die Auswahlstrategie für das dritte Element ist ungefähr:
Wenn die Länge des Arrays kleiner oder gleich 1000 beträgt, wählen Sie das Element an der halben Position als Zielelement.
Wenn die Länge des Arrays 1000 überschreitet, wählen Sie ein Element in einem Abstand von 200-215 (nicht fixiert, ändern sich mit der Länge des Arrays), um zuerst eine Stapel von Kandidatenelementen zu bestimmen. Sortieren Sie dann die Kandidatenelemente in dieser Stapel und verwenden Sie den resultierenden Medianwert als Zielelement.
Nehmen Sie schließlich den mittleren Wert der drei Elemente als Drehzahl.
Beispiel für V8 -Code
var GetThirdIndex = Funktion (a, von, bis) {var t_array = new InternalArray (); // Verwenden Sie beide 'von' und 'zu', um die Pivot -Kandidaten zu bestimmen. var Increment = 200 + ((bis - von) & 15); var J = 0; von += 1; bis -= 1; für (var i = von; i <to; i += inkrement) {t_array [j] = [i, a [i]]; J ++; } t_array.sort (Funktion (a, b) {return compareFn (a [1], b [1]);}); var dritter_index = t_array [t_array.length >> 1] [0]; return dritter_index;}; var quicksort = function QuickSort (a, von, von, bis) {...... while (true) {...... if (bis - von> 1000) {dritter_index = GetThirdIndex (a, von, von, nach); } else {dritter_index = von + ((bis - von) >> 1); }} ......};Sortieren Sie an Ort und Stelle
Bei der Überprüfung des Schnellsortieralgorithmus sah ich viele Beispiele für die Implementierung mit JavaScript im Internet.
Aber ich fand heraus, dass ein großer Teil der Code -Implementierung wie folgt ist
var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var links = []; var rechts = []; für (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {links.push (arr [i]); } else {rechts.push (arr [i]); }} return QuickSort (links) .Concat ([Pivot], QuickSort (rechts));};Das Hauptproblem mit dem obigen Code ist: Verwenden der beiden Zahlenbereiche links und rechts , um rekursive Subtarrays zu speichern, sodass zusätzlichen Speicherplatz von O (n) erforderlich sind. Dies ist ein großer Unterschied im Vergleich zur theoretischen durchschnittlichen räumlichen Komplexität O (n).
Der zusätzliche Space Overhead wirkt sich auch auf die Gesamtgeschwindigkeit der tatsächlichen Laufzeit aus. Dies ist auch einer der Gründe, warum sich die schnelle Sortierung in tatsächlichen Laufzeiten über die gleiche Zeitkomplexität hinaus erfolgen kann. Im Allgemeinen wird das schnelle Sortieren mit einer besseren Leistung eine Innenplätze sortieren.
Die Implementierung im V8 -Quellcode besteht darin, Elemente im ursprünglichen Array auszutauschen.
Warum Firefox die Zusammenführung der Sortierung verwendet
Es steckt auch eine Geschichte dahinter.
Als Firefox am Anfang veröffentlicht wurde, wurde kein stabiler Sortieralgorithmus verwendet, um eine Array -Sortierung zu implementieren, die gut dokumentiert ist.
Der von der Originalversion von Firefox (Firebird) implementierte Array -Sortieralgorithmus war eine Haufensortierung, was auch ein instabiler Sortieralgorithmus ist. Daher hat jemand später einen Fehler eingereicht.
Das Mozilla -Entwicklungsteam hat eine Reihe von Diskussionen zu diesem Thema geführt.
Aus dem Diskussionsprozess können wir einige Punkte ziehen
1. Mozillas Konkurrent im gleichen Zeitraum war IE6. Aus den obigen Statistiken können wir sehen, dass IE6 bei der Sortierung stabil ist.
2.Brendan Eich, der Vater von JavaScript, hält Stabilität gut
3.. Firefox verwendet eine schnelle Sortierung vor der Haufensortierung
Basierend auf der Hauptprämisse, dass Mitglieder der Entwicklungsgruppe tendenziell stabile Sortieralgorithmen implementieren, nimmt Firefox3 die Zusammenführung der Sortierung als neue Implementierung der Array -Sortierung ein.
Lösen Sie die Unterschiede in der Sortierstabilität
Ich habe so viel überdurchschnittlich gesagt, um die Unterschiede in der Sortierumsetzung jedes Browsers zu erkennen und einige der oberflächlicheren Gründe zu erklären, warum diese Unterschiede bestehen.
Aber nach dem Lesen haben die Leser möglicherweise noch Fragen: Was soll ich tun, wenn mein Projekt nur auf stabiles Sortieren verlassen muss?
Lösung
Tatsächlich ist die Idee, dieses Problem zu lösen, relativ einfach.
Der Browser wählt verschiedene Sortieralgorithmen für verschiedene Überlegungen aus. Einige mögen dazu neigen, extreme Leistung zu erzielen, während andere dazu neigen, eine gute Entwicklungserfahrung zu bieten, es sind jedoch Regeln zu befolgen.
Nach der aktuellen bekannten Situation können alle Mainstream -Browser (einschließlich IE6, 7, 8) die Implementierung von Array -Sortieralgorithmen grundsätzlich aufzählen:
1. Sortieren/Timsort zusammenführen
2. Schnelle Sortierung
Wir können also einfach die schnelle Sortierung in eine stabile Sortierung verwandeln?
Im Allgemeinen wirkt sich die Verwendung einer instabilen Sortierung für Objekt -Arrays auf die Ergebnisse aus. Während andere Arten von Arrays selbst stabile oder instabile Sortierergebnisse verwenden. Daher ist der Plan ungefähr wie folgt:
Vorbereitet das zu sortierende Array vorab und füge jedem zu sortierenden Objekt natürliche Ordnungattribute hinzu, um nicht mit anderen Attributen des Objekts in Konflikt zu stehen.
Die Vergleichsmethode für benutzerdefinierte Sortiervergleichsvergleichsmethoden verwendet immer die natürliche Ordnung als zweite Beurteilungsdimension, wenn die Vorurteil gleich ist.
Wenn sich die Implementierungen wie das Zusammenführen der Sortierung gegenübersehen, ändert der zusätzliche Vergleich der natürlichen Ordnung, da der Algorithmus selbst stabil ist.
Es umfasst jedoch die Änderung des Sortierenden Arrays, und es ist zusätzlicher Platz erforderlich, um natürliche Ordnung Eigenschaften zu speichern. Es ist denkbar, dass Motoren wie V8 keine ähnlichen Methoden anwenden sollten. Es ist jedoch als Sortierungsplan machbar, der von Entwicklern angepasst wurde.
Beispiel für Schema -Code
'verwenden strict'; const index = symbol ('index'); function getComparer (compare) {return function (links, rechts) {let result = compare (links, rechts); Rückgabeergebnis === 0? links [Index] - rechts [Index]: Ergebnis; };} Funktionsart (Array, Compare) {Array = array.map ((item, index) => {if (typeof item === 'Objekt') {ideen [index] = index;} return item;}); return array.sort (getComparer (compare));};};Das obige ist nur ein einfaches Beispiel für Algorithmusänderungen, das die stabile Sortierung erfüllt.
Der Grund, warum es einfach ist, ist, dass die Datenstrukturen als Array-Eingaben in der tatsächlichen Produktionsumgebung komplex sind und es notwendig ist, zu beurteilen, ob auf der tatsächlichen Situation mehr Arten der Vorbestellung erforderlich sind.
Etikett
1. Das Front-End ist jetzt ein relativ breites Konzept. Das Front-End in diesem Artikel bezieht sich hauptsächlich auf die Umgebung mit dem Browser als Carrier und JavaScript als Programmiersprache.
2. Dieser Artikel beabsichtigt nicht, den Algorithmus als Ganzes einzubeziehen. Ich möchte gemeinsame Sortieralgorithmen als Einstiegspunkt verwenden.
3. Bei der Bestätigung des Algorithmus, der durch Firefox Array-Sortierung implementiert wurde, wurde in Spidermoney ein Sort-bezogenes Fehler gefunden. Im Allgemeinen schlug jemand während der Diskussion vor, den Timsort -Algorithmus mit einer besseren Leistung in extremen Fällen zu verwenden, um die Zusammenführungssortierung zu ersetzen, aber Mozilla -Ingenieure sagten, dass aufgrund des Problems der Lizenzautorisierung des Timsort -Algorithmus keine Möglichkeit gibt, den Algorithmus in Mozillas Software direkt zu verwenden und auf die nachfolgende Antwort des anderen Partys zu warten.
Zusammenfassen
Das obige ist eine Zusammenfassung und Lösung für die Probleme, die bei der Front-End-Sortierung auftreten. In den letzten Jahren ändern sich immer mehr Projekte in Richtung reicher Kundenanwendungen, und der Anteil des Front-End-Projekts hat zugenommen. Mit der weiteren Verbesserung der Browser -Computerleistung in der Zukunft ermöglicht es einige komplexere Berechnungen. Mit der Änderung der Verantwortlichkeiten kann das Front-End-Formular auch einige größere Änderungen erfahren. Wenn Sie in der Welt gehen, müssen Sie immer eine Fähigkeit haben.