Nach dem Lesen vieler ähnlicher Fragen:
Ich habe noch eine Frage: Angenommen, ich habe ein großes Array von Strings (mehrere tausend), und ich muss viele Lookups machen (d. h. mehrmals prüfen, ob eine gegebene Zeichenkette in diesem Array enthalten ist). Was ist der effizienteste Weg, dies in Node.js zu tun?
A. Sortieren Sie das Array von Strings und verwenden Sie dann die binäre Suche? oder:
B. Konvertieren Sie die Zeichenfolgen in Schlüssel eines Objekts, und verwenden Sie dann den Operator "in"
?
Ich weiß, dass die Komplexität von A O (log N) ist, wobei N die Anzahl der Strings ist.
Aber ich kenne die Komplexität von B nicht.
Wenn ein Javascript-Objekt als Hash-Tabelle implementiert ist, dann ist die Komplexität von B im Durchschnitt 0 (1), was besser ist als A. Allerdings weiß ich nicht, ob ein Javascript-Objekt tatsächlich als implementiert ist eine Hash-Tabelle!
Für ein festes großes Array von Strings empfehle ich eine Form der Radix-Suche Sehen Sie sich auch verschiedene Datenstrukturen und Algorithmen (AVL-Bäume, Warteschlangen / Haufen usw.) in diesem Paket an
Ich bin mir ziemlich sicher, dass die Verwendung von JS-Objekten als Speicher für Zeichenfolgen zu einem "Hash-Modus" für dieses Objekt führt. Abhängig von der Implementierung könnte dies O (log n) bis O (1) Zeit sein. Sehen Sie sich einige jsperf Benchmarks zum Vergleich von Eigenschaftsnachfragen und binärer Suche nach sortierten Arrays.
In der Praxis würde ich, insbesondere wenn ich den Code nicht im Browser verwende, diese Funktionalität auf etwas wie redis oder memcached abladen.
Aktualisierung für 2016
Da Sie nach node.js fragen und es 2016 ist, können Sie jetzt entweder das Objekt Set oder Map von ES6 verwenden, da diese in ES6 integriert sind. Beides erlaubt Ihnen, eine beliebige Zeichenfolge als Schlüssel zu verwenden. Das Objekt Set ist geeignet, wenn Sie nur sehen möchten, ob der Schlüssel wie folgt existiert:
Und Map ist geeignet, wenn Sie einen Wert für diesen Schlüssel wie in:
Beide ES6-Funktionen sind ab Knoten V4 jetzt in node.js integriert (die aktuelle Version von node.js ab dieser Änderung ist v6).
Siehe diesen Leistungsvergleich , um zu sehen, um wieviel schneller der Set Operationen sind als viele andere Möglichkeiten.
Ältere Antwort
Alle wichtigen Leistungsfragen sollten mit tatsächlichen Leistungstests in einem Tool wie jsperf.com getestet werden. In Ihrem Fall verwendet ein JavaScript-Objekt eine Hash-Table-ähnliche Implementierung, denn ohne etwas, das ziemlich gut funktioniert, wäre die gesamte Implementierung langsam, da JavaScript so oft Objekte verwendet.
String-Tasten an einem Objekt wären das Erste, was ich testen würde, und ich würde meinen, dass es sich um den besten Darsteller handelt. Da die Interna eines Objekts in nativem Code implementiert sind, würde ich erwarten, dass dies schneller ist als Ihre eigene Hashtabellen- oder Binärsuche, die in JavaScript implementiert wird.
Aber, als ich meine Antwort mit begann, sollten Sie wirklich Ihre spezifischen Umstände mit der Anzahl und Länge der Zeichenfolgen prüfen, die Sie in einem Werkzeug wie jsperf am meisten interessieren.
Tags und Links node.js performance