JavaScript-Objekte als Hashes? Ist die Komplexität größer als O (1)?

Für einige Algorithmus, den ich schrieb vor kurzem dachte ich, dass ein hash wäre hervorragend. Ich dachte, dass ich könnte wahrscheinlich nur verwenden Sie die member-Variablen in einem Objekt als Schlüssel-Wert-Paare. Ich bin nicht sicher, ob dies optimal ist, da ich nicht wirklich weiß, was Los ist hinter den kulissen. Ich habe auch angenommen, dass der V8 macht es anders als andere Umgebungen. Ich weiß allerdings vorstellen, dass suchen-member-Variablen wäre ziemlich schnell (hoffentlich)?

Dass alles gesagt Frage ich mich, ob die Laufzeit-Komplexität von schreiben, Lesen, erstellen und löschen von member-Variablen in JavaScript-Objekte sind alle O(1). Wenn es Unterschiede in der Umwelt (v8 vs andere), was sind Sie?

Kommentar zu dem Problem
Dies scheint ein bisschen wie ein Thema für fortgeschrittene, also es ist unwahrscheinlich, dass jemand schon die jüngsten in-depth-Analyse von diesem. Ich denke, Sie sind auf Ihre eigenen, so schlage ich vor, Sie schreiben einen einfachen Maßstab, versuchen Sie es heraus auf den verschiedenen Browsern, dann posten Sie die Ergebnisse in einer Antwort auf diese Frage. Es sollte Sie nicht mehr als 30 Minuten. Kommentarautor: Dai
Wenn Sie möchten, um die Suche für Ihr Objekt von einigen Feld, warum Sie sich sorgen über das hinzufügen und entfernen? ID ist eigentlich nicht zu ändern, nach der Objekt-Instanziierungen. Kommentarautor: aviad
@aviad ich nehme an, das hinzufügen und das entfernen ist nicht so ein großes Angebot. Ich sehe nicht ein Fall für mehr als ein paar Millionen Paare, und sogar das ist den meisten wahrscheinlich lächerlich für diesen Anwendungsfall im besonderen. Dann wieder, die Menschen verwenden möchten, können diese spezifische Funktion für andere Dinge. Ich würde gerne einige Hinweise. Kommentarautor: Parris
"verwenden Sie die member-Variablen in einem Objekt als Schlüssel-Wert-Paare" - Das ist ziemlich viel, was die "member-Variablen" sind, ist es nicht? Kommentarautor: nnnnnn
@nnnnnn auch ich habe nicht unbedingt gesehen keine Garantien über die Leistung. Sie sind Schlüssel-Wert-Paare, aber Sie können sagen, dass über jede variable in jeder Sprache. Kommentarautor: Parris

InformationsquelleAutor der Frage Parris | 2012-09-03

  1. 48

    UPDATE

    Chrome löschen, ist nun wirklich speedy; aber update scheint langsamer zu werden, wenn Sie, wie Sie Ansatz 1 Millionen keys.

    Okay, ich habe einige Daten. Ich werde sagen, ja, es gibt Unterschiede zwischen den Browsern. Es scheint, dass verschiedene Umgebungen Betreuung über die verschiedenen CRUD-Operationen. Auch die Objekte hashes unter der Haube, da die Leistung wird nicht beeinträchtigt, wenn die Anzahl der Tasten erhöht. Wenn es keine performance-Unterschied (ops/sec) zwischen den 3 Proben dann (glaube ich), dass heißt, es ist ein hash und die Komplexität der operation ist O(1) unabhängig davon, dass es schneller oder langsamer im Vergleich zu anderen Operationen. In anderen Worten, wenn es eine änderung in der test - ops/sec zählen als Schlüssel erhöhen, dann ist es nicht O(1) (dies ist nicht der Fall).

    Tests:

    http://jsperf.com/objectsashashes/2 (100 keys)

    http://jsperf.com/objectsashashes/3 (100k keys)

    http://jsperf.com/objectsashashes/ (1 Mio keys)

    http://jsperf.com/objects-as-hashes-300-mil (10-Tasten)

    Beobachtungen:

    • Zeit zu erstellen-Paaren wird linear über 10 mil-Schlüssel-Wert-Paare.
    • Chrome: Optimiert für liest. Erstellen und Aktualisieren, sind ein wenig langsamer.
    • Safari: Optimiert für schreibt, aber Lesen ist ziemlich schnell. Langsamer zu aktualisieren scheint.
    • IE9: Bevorzugt keine der Operationen. Löschen ergibt etwas bessere Leistung. Hinweis: ich habe eine ältere Maschine zu testen.
    • IE10: Löschen Renditen etwas bessere Leistung. Erstellung/Aktualisierung langsamer als das Lesen.
    • IE8: Konnte es nicht testen, aber mit dem letzten win7 updates scheint es, dass der IE9 wurde automatisch installiert. Nicht sicher über die XP-Maschinen.
    • Firefox: Extrem Lesen optimiert. Alles andere ist in etwa gleich.
    • Oper: Alle Operationen ausführen, bei gleicher Geschwindigkeit.
    • Die einzigen Einschränkungen für die maximale Schlüssel gespeichert zu sein scheinen, Speicher-basiert (browser, Umwelt oder Maschine erzwungen)

    Abschließende Bemerkungen:

    Obwohl hash['irgendwas'] ist nicht langsamer als hash.etwas, wenn Sie brauchen, um zu verketten, um den Namen Ihres hash-Ihre Leistung wird drastisch reduziert ( http://jsperf.com/member-associative-array-syntax-vs-dot-syntax ), das ist der Grund, warum ich zwischengespeichert, die diese Werte außerhalb des performance-tests vor. Vermeiden Verkettung, wenn möglich. Strings sind unveränderlich in JS, und als ein Ergebnis jede Verkettung erstellt 3 Objekte/"primitive" (string 1, string 2 und die verkettete Zeichenfolge).

    InformationsquelleAutor der Antwort Parris

  2. 6

    JavaScript-Objekte sind hashes. Ich kann mir nicht vorstellen, jeder vernünftige Umsetzung, wäre es nicht konstant-die Zeit der CRUD-Operationen auf Objekt-Eigenschaften.

    Sehen Sie spezifische performance-Probleme bei diesem Ansatz?

    InformationsquelleAutor der Antwort Matt Ball

Schreibe einen Kommentar