Der Autor des Materials, dessen Übersetzung wir heute veröffentlichen, ist zuversichtlich, dass viele JavaScript-Entwickler hauptsächlich Datentypen wie
Number ,
String ,
Object ,
Array und
Boolean . In den meisten Fällen ist dies ausreichend. Wenn Sie den Code jedoch so schnell und skalierbar wie möglich gestalten müssen, ist die Verwendung dieser Datentypen nicht immer gerechtfertigt.
In diesem Artikel werden wir darüber sprechen, wie mithilfe des Datentyps
Set , der die Möglichkeit bietet, mit Sammlungen eindeutiger Werte zu arbeiten, Code schneller wird. Dies gilt insbesondere für den Code von Großprojekten. Die
Array und
Set haben viele Gemeinsamkeiten, aber die Verwendung des Datentyps
Set kann dem Programmierer solche Funktionen bieten, die sich bei der Ausführung von Programmen deutlich manifestieren, die der
Array Typ nicht hat.
Was ist der Unterschied zwischen den Datentypen Array und Set?
Das Hauptmerkmal des
Array Datentyps (wir werden Objekte dieses Typs "Arrays" nennen) ist, dass Arrays indizierte Wertesammlungen sind. Dies bedeutet, dass Daten in Arrays mithilfe von Indizes gespeichert werden.
const arr = [A, B, C, D]; console.log(arr.indexOf(A));
Im Gegensatz zu Arrays sind Objekte vom Typ
Set (wir nennen sie "Sammlungen") Sammlungen, die Daten im Schlüssel- / Wertformat enthalten. Anstatt Indizes zu verwenden, speichern Sammlungen Elemente mithilfe von Schlüsseln. In der Sammlung gespeicherte Elemente können in der Reihenfolge sortiert werden, in der sie der Sammlung hinzugefügt wurden, während die Sammlung nicht dieselben Elemente speichern kann. Mit anderen Worten, alle Elemente der Sammlung müssen eindeutig sein.
Was sind die Hauptstärken der Kollektionen?
Wenn Sie Sammlungen und Arrays vergleichen, können Sie einige Vorteile gegenüber Sammlungen gegenüber Arrays feststellen, insbesondere in Situationen, in denen die Programmleistung wichtig ist:
- Nach Artikeln suchen. Die Array-Methoden
indexOf() und indexOf() , mit denen nach Elementen indexOf() und indexOf() wird, ob ein Element ein Element enthält, arbeiten langsam. - Elemente entfernen. Ein Element kann basierend auf seinem Wert in der Sammlung gelöscht werden. In einem Array besteht das Äquivalent einer solchen Aktion darin, die
splice() -Methode zu verwenden, die auf dem Index des Elements basiert. Wie bei der Elementsuche ist das Entfernen von Elementen mithilfe von Indizes ein langsamer Vorgang. - Fügen Sie einen Artikel ein. Das Hinzufügen eines Elements zur Sammlung ist viel schneller als die Verwendung von Methoden wie
push() und unshift() in einem Array. - Arbeiten Sie mit dem
NaN Wert. Die indexOf() -Methode kann nicht zum indexOf() des NaN Werts in einem Array verwendet werden. Mit der has() -Sammlungsmethode können Sie feststellen, ob NaN darin enthalten ist. - Doppelte Elemente entfernen.
Set Objekte speichern nur eindeutige Werte. Wenn Sie vermeiden möchten, doppelte Elemente in einer Datenstruktur zu speichern, ist dies ihr wesentlicher Vorteil gegenüber Arrays. Wenn Sie mit Arrays arbeiten, um doppelte Elemente zu entfernen, müssen Sie zusätzlichen Code schreiben.
Eine vollständige Liste der integrierten Methoden für Objekte vom Typ
Set finden Sie
hier .
Zur zeitlichen Komplexität von Algorithmen
Die Methoden, mit denen Arrays nach Elementen suchen, haben eine lineare Zeitkomplexität - O (N). Mit anderen Worten ist die Elementsuchzeit proportional zur Größe des Arrays.
Im Gegensatz zu Arrays weisen die von Sammlungen zum Suchen, Löschen und Hinzufügen von Elementen verwendeten Methoden eine zeitliche Komplexität von O (1) auf. Dies bedeutet, dass die Größe der Sammlung praktisch keinen Einfluss auf die Arbeitszeit solcher Methoden hat.
Hier können Sie mehr über die zeitliche Komplexität der Algorithmen lesen.
Wie viel schneller sind Sammlungen als Arrays?
Obwohl die Leistungsindikatoren von JavaScript-Code stark von einer Vielzahl von Faktoren beeinflusst werden, hängen sie insbesondere vom System ab, auf dem der Code ausgeführt wird, von der verwendeten Codelaufzeit und von der Größe der verarbeiteten Daten. Ich hoffe, dass die Ergebnisse meiner Tests Ihnen die Möglichkeit geben, Arrays und Sammlungen zu vergleichen aus praktischer Sicht und verstehen, wie Sammlungen schneller als Arrays sind. Nun werden wir drei einfache Tests betrachten und ihre Ergebnisse analysieren.
PreparationTestvorbereitung
Bevor Sie Tests durchführen, erstellen wir ein Array mit einer Million Elementen und derselben Sammlung. Der Einfachheit halber verwenden wir einen Zyklus, dessen erster Zählerwert 0 und dessen letzter - 999999 ist:
let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); }
▍Test Nr. 1: Überprüfen, ob ein Element in einem Array und in einer Sammlung vorhanden ist
Zuerst werden wir prüfen, ob das Element
123123 im Array und in der Sammlung vorhanden ist, wobei wir im Voraus wissen, dass ein solches Element in diesen Datenstrukturen vorhanden ist.
let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set');
Hier sind die Ergebnisse dieses Tests:
Array: 0.173ms Set: 0.023ms
Die Sammlung ist 7,54-mal schneller als das Array.
▍Test Nr. 2: Einfügen eines Elements
Versuchen wir nun, Arrays und Sammlungen Elemente hinzuzufügen.
console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set');
Folgendes ist passiert:
Array: 0.018ms Set: 0.003ms
Die Sammlung ist 6,73-mal schneller als das Array.
▍Test 3: Löschen Sie ein Element
Entfernen wir nun das Element aus jeder Datenstruktur (z. B. das im vorherigen Test hinzugefügte). Arrays verfügen nicht über eine integrierte Methode zum Löschen von Elementen. Daher erstellen wir eine Hilfsfunktion, um unseren Code in gutem Zustand zu halten:
const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); };
Und hier ist der Testcode:
console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set');
Das Ergebnis ist folgendes:
Array: 1.122ms Set: 0.015ms
In diesem Fall war die Sammlung 74,13-mal schneller als das Array!
Im Allgemeinen kann festgestellt werden, dass die Codeleistung durch die Verwendung von Sammlungen anstelle von Arrays erheblich gesteigert werden kann. Betrachten Sie einige praktische Beispiele.
Beispiel 1: Entfernen doppelter Werte aus einem Array
Wenn Sie doppelte Werte schnell aus einem Array entfernen müssen, können Sie sie in eine Sammlung konvertieren. Dies ist vielleicht der einfachste Weg, um doppelte Werte loszuwerden:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
Beispiel 2: Interviewaufgabe bei Google
In einem meiner
Materialien habe ich vier Möglichkeiten zur Beantwortung der von einem Interviewer von Google gestellten Frage untersucht. Das Interview wurde mit C ++ geführt, aber wenn JavaScript anstelle dieser Sprache verwendet würde, würde die
Set Datenstruktur notwendigerweise zur Lösung des Problems verwendet.
Wenn Sie die Antwort auf diese Frage besser verstehen möchten, lesen Sie den obigen Artikel. Hier zeige ich nur eine fertige Lösung.
▍ Aufgabe
Gegeben ein unsortiertes Array von ganzen Zahlen und einen
sum . Schreiben Sie eine Funktion, die
true zurückgibt
true wenn wir durch Hinzufügen von zwei Elementen dieses Arrays den
sum . Wenn das Array keine solchen Elemente enthält, sollte die Funktion
false .
Es stellt sich zum Beispiel heraus, dass die Funktion
true sollte, wenn wir ein Array
[3, 5, 1, 4] und der
sum 9 ist, da
4+5=9 .
▍Lösung
Sie können dieses Problem mit der folgenden Idee lösen: Sie müssen das Array durchlaufen und die sortierte
Set Datenstruktur erstellen, in die Werte hinzugefügt werden, die die gefundenen Werte zum
sum ergänzen.
Lassen Sie uns diese Idee am Beispiel des obigen Arrays analysieren. Wenn wir
3 treffen, können wir die Nummer
6 zur Sammlung hinzufügen, da wir wissen, dass wir zwei Zahlen finden müssen, die insgesamt
9 . Jedes Mal, wenn wir auf einen neuen Wert aus dem Array stoßen, können wir die Sammlung überprüfen und feststellen, ob sie vorhanden ist. Wenn wir die Nummer
5 treffen, werden wir der Sammlung
4 hinzufügen. Und wenn wir endlich die Nummer
4 , finden wir sie in der Sammlung und können
true .
So könnte eine Lösung für dieses Problem aussehen:
const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) { let searchVal = val - arr[i]; if (searchValues.has(arr[i])) { return true; } else { searchValues.add(searchVal); } }; return false; };
Und hier ist eine präzisere Lösung:
const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
Da die zeitliche Komplexität der
Set.prototype.has() -Methode O (1) ist, können Sie mithilfe der
Set Datenstruktur zum Speichern von Zahlen, die die im Array gefundenen Zahlen zu einem bestimmten Wert ergänzen, eine Lösung in linearer Zeit (O (N)) finden.
Wenn die Lösung von der Methode
Array.prototype.indexOf() oder von der Methode
Array.prototype.includes() , deren zeitliche Komplexität jeweils O (N) beträgt, wäre die Gesamtzeitkomplexität des Algorithmus O (N
2 ). Infolgedessen würde er viel langsamer werden.
Zusammenfassung
Wenn Sie den Datentyp
Set noch nicht in JavaScript gefunden haben, hoffen wir, dass Sie ihn jetzt, wenn Sie eine Vorstellung davon haben, in Ihren Projekten mit Nutzen verwenden können.
Liebe Leser! Wie würden Sie die
Set Datenstruktur in Ihrem Code anwenden?