Erneute Diskussion der Leistungsoptimierung von JavaScript-Arrays

JavaScript-Array-Deduplizierung erscheint häufig in schriftlichen Testfragen für Front-End-Rekrutierungen, zum Beispiel:

Es gibt ein Array var arr = ['a', 'b', 'c', '1' , 0, ' c', 1, '', 1, 0], bitte verwenden Sie JavaScript, um die Deduplizierungsfunktion unqiue zu implementieren, sodass unique(arr) ['a', 'b', 'c', '1', 0, 1, ' ']

Als schriftliche Testfrage gibt es zwei Testpunkte:

1. Unterschätzen Sie diesen Testpunkt nicht. Wenn man bedenkt, dass JavaScript häufig in Browsern ausgeführt wird, ist es keine leichte Aufgabe, die Korrektheit einer Funktion in verschiedenen Browserumgebungen sicherzustellen. Wenn Sie mir nicht glauben, lesen Sie diesen Blog weiter.

2. Leistung. Obwohl die JavaScript-Sprache selbst (im engeren Sinne, mit Ausnahme von Erweiterungen wie DOM) in den meisten Fällen keine Leistungsprobleme verursacht, handelt es sich leider um eine Prüfungsfrage, sodass Interviewer die Leistung dennoch als Testpunkt betrachten.

Bevor Sie weiterlesen, empfehlen wir Ihnen, eine Version zu implementieren, die Sie für die beste halten.

Intuitive Lösung

Für die Array-Deduplizierung können Sie, sofern Sie ein Programm geschrieben haben, sofort die erste Lösung erhalten:

function unique( arr ) {

var ret = []

for (var i = 0; i < arr.length; i++) {

var item = arr[i]

if (ret.indexOf(item) === -1) {

ret.push(item)

}

}

return ret

}

In modernen Browsern ist die oben genannte Funktion sehr korrekt und weist eine gute Leistung auf . . Die größte Tragödie und Herausforderung des Frontends besteht jedoch darin, dass es verschiedene Betriebsumgebungen unterstützen muss. Unter IE6-8 existiert die indexOf-Methode für Arrays noch nicht. Die intuitive Lösung muss leicht modifiziert werden:

var indexOf = [].indexOf ?

function(arr, item) {

return arr .indexOf (item)

} :

function indexOf(arr, item) {

for (var i = 0; i < arr.length; i++) {

                                                                                                                                                                                                                                       

}

function unique(arr) {

var ret = []

for (var i = 0; i < arr.length; i++) {

var item = arr[i]

if (indexOf(ret, item) === -1 ). 🎜>

schreiben An diesem Punkt ist die Korrektheit kein Problem mehr, aber in Bezug auf die Leistung wird die Doppelschleife die Interviewer unglücklich machen.

Optimierungsplan

Wenn es um Optimierung geht, passiert es oft, dass die acht Unsterblichen das Meer überqueren und hundert Blumen blühen. Doch die Acht Unsterblichen sind oft nicht bodenständig und die Hundert Blumen können leicht Bettwanzen anlocken. Die verschiedenen Optimierungslösungen für die Array-Deduplizierung werden hier nicht einzeln besprochen. Wir sprechen hier nur über die am häufigsten verwendete Lösung mit sehr guten Ergebnissen.

function unique(arr) {

var ret = []

var hash = {}

for (var i = 0; i < arr.length; i++) {

var item = arr[i]

var key = typeof(item) + item

if (hash[key] !== 1) {

ret.push(item)

hash[key] = 1

}

}

return ret

}

Der Kern besteht darin, ein Hash-Objekt zu erstellen, um indexOf zu ersetzen des Objekts Es kann nur eine Zeichenfolge sein, daher wird var key = typeof(item) + item benötigt, um zwischen dem Wert 1 und der Zeichenfolge „1“ zu unterscheiden.

Aber die Optimierung kann wirklich leicht zu Fallstricken führen. In der obigen Implementierung ist es beispielsweise unmöglich, die folgende Eingabe zu beurteilen:

1

unique([ neuer String (1 ), neue Nummer(1) ])

Sie können den Code weiterhin ändern, um eine gute Leistung und Korrektheit zu erzielen. Aber oft sind die Ergebnisse nicht gut.

Echte Bedürfnisse

Nachdem ich dies geschrieben habe, kann dieser Blog zur Sache kommen. Alle Programmierer haben einige Träume im Herzen, wie zum Beispiel das Schreiben universeller Funktionen mit guter Gesamtleistung und guter Leistung. Diese Art von Traum ist eine wichtige treibende Kraft für Programmierer, um exzellent zu werden. Wenn sie jedoch nicht kontrolliert wird, kann sie leicht in die Irre gehen.

Zurück zur Leistungsoptimierung. Heutzutage gibt es verschiedene Optimierungen, darunter Kernsysteme, Datenbanken, Netzwerke, Frontends usw. Alle diese Optimierungen müssen die folgende Frage beantworten:

1. Was ist derzeit verfügbar? In welchem ​​Szenario sollte die Optimierung durchgeführt werden und welche spezifischen Einschränkungen gelten für das Szenario? Es ist wichtig, Einschränkungen zu überwinden, die oft Freiheit mit sich bringen.

2. Was genau möchtest du? Was ist der Zweck der Optimierung? Ob es darum geht, die Stabilität zu verbessern, den Durchsatz zu erhöhen oder die Wartezeit der Benutzer zu verkürzen. Bis diese Frage beantwortet ist, ist Optimierung vergeblich. Eine genaue Antwort auf diese Frage kann konkrete messbare Parameter in die Optimierung einbringen, sodass die Optimierung Ziele haben kann.

3. Worauf kannst du verzichten? Du kannst deinen Kuchen nicht haben und ihn gleichzeitig essen. Der Kern der Optimierung besteht in Entscheidungen und Kompromissen in bestimmten Szenarien. Wer nicht bereit ist, auf etwas zu verzichten, dem fällt die Optimierung oft schwer.

Beim Schreiben dieses Blogs geht es nicht darum, die schriftliche Testfrage zu beantworten. Diese schriftliche Testfrage ist etwas langweilig. Der ursprüngliche Antrieb für das Schreiben dieses Blogs ist, dass ich kürzlich die Leistung von SeaJS optimiert habe. Eine der Anforderungen ist:

define(function(require, exports) {

var a = require('./a')

var b = require('./b')

...

require('. / a').fn(...)

})

Das Obige ist ein Modul. Durch Parsen der Funktionszeichenfolge können Sie das Abhängigkeitsarray des Moduls erhalten: ['./a ', './b', './a'], diese Abhängigkeitsinformationen können doppelte Felder enthalten, daher müssen Duplikate entfernt werden.

Beantworten wir für dieses spezielle Szenario die oben genannten drei Fragen:

1. Was ist derzeit verfügbar? Es gibt einige Eingabebeschränkungen, es müssen nur Zeichenfolgen berücksichtigt werden.

2. Was genau möchtest du? Dieses Problem ist relativ einfach. Der Indikator besteht darin, das Profilfenster im Chrome-Debugging-Tool zu verwenden, um die Zeit anzuzeigen, die die einzigartige Methode auf der angegebenen Testseite benötigt 5ms.

3. Worauf kannst du verzichten? Es müssen nur Zeichenfolgen verarbeitet werden, andere Typen werden nicht unterstützt. Es ist oft interessant, über das Aufgeben zu sprechen. Dieses Problem ist nicht so einfach, also lasst uns als nächstes darüber reden.

Lösung unter SeaJS

Sobald das spezifische Szenario klar analysiert ist, ist die Lösung relativ einfach:

function unique(arr) {

var obj = {}

forEach(arr, function(item) {

obj[item] = 1

})

return key(obj)

}

Der obige Code basiert auf forEach und Schlüsseln und kann nicht vom Kontext getrennt werden (die Umgebung ist sehr wichtig), vollständiger Code: util-lang.js

Die obige Lösung ist in Bezug auf Codegröße, Korrektheit und Gesamtleistung unter verschiedenen Browsern sehr gut.

Bis eines Tages ein solcher Testfall auftauchte:

define(function(require, exports) {

var a = require('toString' )

var b = require('hasOwnProperty')

...

})

Die „perfekte“ Lösung

Der obige Testfall ruft

unique([ 'toString', 'hasOwnProperty' ]) auf // Es wird erwartet, dass [ 'toString', 'hasOwnProperty' ]

zurückgegeben wird IE hat verschiedene Fehler, hier ist ein weniger bekannter, aber echter:

var obj = { toString: 1, hasOwnProperty: 1 }

for (var p in obj ) {

console.log(p)

}

Unter modernen Browsern werden die beiden Werte korrekt ausgegeben, aber in Old Es erfolgt keine Ausgabe unter IE. Dies ist ein Aufzählungsfehler im IE: Eine sicherere Object.keys-Kompatibilitätsimplementierung. Die „perfekte“ Lösung lautet wie folgt:

var keys = Object.keys || (function () {

var hasOwnProperty = Object.prototype.hasOwnProperty,

hasDontEnumBug = !{toString:null}.propertyIsEnumerable("toString"),

DontEnums = [

'toString',

'toLocaleString',

'valueOf',

'hasOwnProperty',

'is PrototypeOf',

'propertyIsEnumerable',

'constructor'

],

DontEnumsLength = DontEnums.length;

Rückgabefunktion ( o) {

if (typeof o != "object" && typeof o != "function" || o === null)

throw new TypeError("Object.keys aufgerufen ein Nichtobjekt");

var result = [];

for (var name in o) {

if (hasOwnProperty.call (o , name))

                 result.push(name); 🎜>                                                                                                                                           ;

Zusätzlich zum DontEnums-Array , können Sie auch besonderes Augenmerk auf die Handhabung von hasOwnProperty legen. **Für das Frontend ist es nicht einfach, die „Korrektheit“ sicherzustellen. **