Großes O von JavaScript-Arrays

Arrays in JavaScript können sehr einfach durch Hinzufügen und Entfernen von Elementen geändert werden. Es maskiert etwas die Tatsache, dass die meisten Spracharrays eine feste Größe haben und komplexe Operationen erfordern, um die Größe zu ändern. Es scheint, dass JavaScript es einfach macht, Array-Code mit schlechter Leistung zu schreiben. Dies führt zu der Frage:

Welche Leistung (in Bezug auf die große O-Zeit-Komplexität) kann ich von JavaScript-Implementierungen in Bezug auf die Array-Leistung erwarten?

Ich gehe davon aus, dass alle vernünftigen JavaScript-Implementierungen höchstens die folgenden großen O's haben.

• Zugang - O (1)
• Anhängen - O (n)
• Voranstellen - O (n)
• Einfügung - O (n)
• Löschen - O (n)
• Tauschen - O (1)

Mit JavaScript können Sie ein Array mithilfe der new Array(length)Syntax bis zu einer bestimmten Größe vorfüllen. (Bonusfrage: Erstellt ein Array auf diese Weise O (1) oder O (n)) Dies ähnelt eher einem herkömmlichen Array und kann bei Verwendung als Array mit Vorgröße das Anhängen von O (1) ermöglichen. Wenn eine zirkuläre Pufferlogik hinzugefügt wird, können Sie O (1) voranstellen. Wenn ein dynamisch expandierendes Array verwendet wird, ist O (log n) der durchschnittliche Fall für beide.

Kann ich für einige Dinge eine bessere Leistung erwarten als hier angenommen? Ich erwarte nicht, dass irgendetwas in irgendwelchen Spezifikationen beschrieben ist, aber in der Praxis könnte es sein, dass alle wichtigen Implementierungen hinter den Kulissen optimierte Arrays verwenden. Gibt es dynamisch expandierende Arrays oder andere leistungssteigernde Algorithmen?

PS

Der Grund, warum ich mich frage, ist, dass ich einige Sortieralgorithmen erforsche, von denen die meisten davon ausgehen, dass das Anhängen und Löschen O (1) -Operationen sind, wenn ich ihr gesamtes großes O beschreibe.

_{HINWEIS: Obwohl diese Antwort 2012 richtig war, verwenden Engines heute sehr unterschiedliche interne Darstellungen für Objekte und Arrays. Diese Antwort kann wahr sein oder nicht.}

Im Gegensatz zu den meisten Sprachen, die Arrays mit Arrays implementieren, sind Arrays in Javascript Arrays Objekte, und Werte werden wie reguläre Objektwerte in einer Hashtabelle gespeichert. So wie:

• Zugang - O (1)
• Anhängen - Amortisiertes O (1) (manchmal ist eine Größenänderung der Hashtabelle erforderlich; normalerweise ist nur das Einfügen erforderlich)
• Voranstellen von - O (n) über unshift, da alle Indizes neu zugewiesen werden müssen
• Einfügung - Amortisiertes O (1), wenn der Wert nicht vorhanden ist. O (n), wenn Sie vorhandene Werte verschieben möchten (z splice. B. mit ).
• Löschen - Amortisiert O (1), um einen Wert zu entfernen, O (n), wenn Sie Indizes über neu zuweisen möchten splice.
• Tauschen - O (1)

Im Allgemeinen wird das Setzen oder Deaktivieren eines Schlüssels in einem Diktat mit O (1) amortisiert, und das Gleiche gilt für Arrays, unabhängig davon, um welchen Index es sich handelt. Jede Operation, bei der vorhandene Werte neu nummeriert werden müssen, ist O (n), nur weil Sie alle betroffenen Werte aktualisieren müssen.

Garantie

Es gibt keine festgelegte Zeitkomplexitätsgarantie für eine Array-Operation. Die Leistung von Arrays hängt von der zugrunde liegenden Datenstruktur ab, die die Engine auswählt. Motoren können auch unterschiedliche Darstellungen haben und je nach Heuristik zwischen ihnen wechseln. Die anfängliche Arraygröße kann eine solche Heuristik sein oder auch nicht.

Wirklichkeit

Beispielsweise verwendet V8 (ab heute) sowohl Hashtabellen als auch Array-Listen , um Arrays darzustellen. Es gibt auch verschiedene Darstellungen für Objekte, sodass Arrays und Objekte nicht verglichen werden können. Daher ist der Array-Zugriff immer besser als O (n) und möglicherweise sogar so schnell wie ein C ++ - Array-Zugriff. Das Anhängen ist O (1), es sei denn, Sie erreichen die Größe der Datenstruktur und sie muss skaliert werden (was O (n) ist). Vorbereiten ist schlimmer. Das Löschen kann noch schlimmer sein, wenn Sie so etwas tun delete array[index](nicht!), Da dies die Engine dazu zwingen könnte, ihre Darstellung zu ändern.

Rat

Verwenden Sie Arrays für numerische Datenstrukturen. Dafür sind sie gedacht. Dafür werden Motoren optimiert. Vermeiden Sie spärliche Arrays (oder wenn Sie müssen, erwarten Sie eine schlechtere Leistung). Vermeiden Sie Arrays mit gemischten Datentypen (da dies die internen Darstellungen komplexer macht ).

Wenn Sie wirklich für eine bestimmte Engine (und Version) optimieren möchten, überprüfen Sie den Quellcode auf die absolute Antwort.