Zeitliche Komplexität von unshift () vs. push () in Javascript

70

Ich weiß, was der Unterschied zwischen unshift()und push()Methoden in JavaScript ist, aber ich frage mich, was der Unterschied in der zeitlichen Komplexität ist.

Ich nehme an, dass die push()Methode O (1) ist, weil Sie nur ein Element am Ende des Arrays hinzufügen, aber ich bin mir nicht sicher unshift(), ob die Methode alle anderen vorhandenen Elemente vorwärts "verschieben" muss, und ich nehme an das ist O (log n) oder O (n)?

Dperitch
quelle
Was meinst du mit zeitlicher Komplexität? Ausführungszeit?
i--
Mit einer Smart-Sparse-Array-Implementierung unshiftkönnte die Zeit nahezu konstant sein, aber ich muss mich fragen, ob es sich lohnt, den normalen Array-Zugriff zu erschweren. Ich persönlich glaube nicht, dass ich jemals einen Anruf an geschrieben habe unshift.
Pointy
15
@therao - Er meint die Standarddefinition der Informatik in Big-O-Begriffen.
Nemo

Antworten:

24

Die JavaScript-Sprachspezifikation schreibt meines Wissens nicht die zeitliche Komplexität dieser Funktionen vor.

Es ist sicherlich möglich, eine Array-ähnliche Datenstruktur (O (1) Direktzugriff) mit O (1) pushund unshiftOperationen zu implementieren . Das C ++ std::dequeist ein Beispiel. Eine Javascript-Implementierung, die C ++ - Deques verwendet, um Javascript-Arrays intern darzustellen, hätte daher O (1) pushund unshiftOperationen.

Aber wenn Sie solche Zeitgrenzen garantieren müssen, müssen Sie Ihre eigenen rollen, wie folgt:

http://code.stephenmorley.org/javascript/queues/

Nemo
quelle
4
Wie komplex ist V8?
Light24bulbs
64

push () ist schneller.

js>function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
js>foo()
2190
js>function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
js>bar()
10


Aktualisieren

Das Obige berücksichtigt nicht die Reihenfolge der Arrays. Wenn Sie sie richtig vergleichen möchten, müssen Sie das Push-Array umkehren. Allerdings ist das Drücken und Rückwärtsfahren 10msfür mich auf Chrom mit diesem Snippet immer noch schneller :

var a=[]; 
var start = new Date; 
for (var i=0;i<100000;i++) {
  a.unshift(1);
}
var end = (new Date)-start;
console.log(`Unshift time: ${end}`);

var a=[];
var start = new Date;
for (var i=0;i<100000;i++) {
  a.push(1);
}

a.reverse();
var end = (new Date)-start;
console.log(`Push and reverse time: ${end}`);

Shanti
quelle
Je größer der Satz, desto größer der Unterschied auf meinem Computer, Macpro, bei Verwendung des obigen @ Shanti-Codes, wobei i <150000 Unshift mehr als 250-mal langsamer ist. Die weiter oben genannten jsperf-Beispiele verwenden Arrays mit nur 4 Elementen.
Snowcode
1
@TheHe scheint jedoch richtig zu sein, mein erster Test wurde auf Chrome ausgeführt (mein Kommentar oben), dann habe ich denselben Test auf demselben Computer auf Safari ausgeführt und push(...)war 10% schneller. Ich hatte keinen so großen Unterschied zwischen Javascript-Engines erwartet. Huh! (Ich habe gerade festgestellt, dass dieses Q 2 Jahre alt ist und Safari einen langen Weg zurückgelegt hat, den ich Safari 7.1.6für das MacPro 2014-Modell verwende.)
Snowcode
Verschieben / Verschieben 94% langsamer als Push / Pop auf Chrome 48 Win10.
Chris Moschini
1
Wenn jemand neugierig ist, ist die Verwendung pushmit shiftschneller als unshiftmit pop.
Douggard
Auf Safari unshiftdauert 13.0 8ms und pushdauert 3ms
Akrogenese
9

Für Leute, die neugierig auf die v8-Implementierung sind, ist hier die Quelle . Da unshifteine beliebige Anzahl von Argumenten verwendet wird, verschiebt sich das Array selbst, um alle Argumente aufzunehmen.

UnshiftImplendet Aufruf AddArgumentsmit einem start_positionvon AT_STARTihm zu diesem welche Tritte elseAussage

  // If the backing store has enough capacity and we add elements to the
  // start we have to shift the existing objects.
  Isolate* isolate = receiver->GetIsolate();
  Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0,
                         length, 0, 0);

und bringt es zum MoveElements.

  static void MoveElements(Isolate* isolate, Handle<JSArray> receiver,
                           Handle<FixedArrayBase> backing_store, int dst_index,
                           int src_index, int len, int hole_start,
                           int hole_end) {
    Heap* heap = isolate->heap();
    Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store);
    if (len > JSArray::kMaxCopyElements && dst_index == 0 &&
        heap->CanMoveObjectStart(*dst_elms)) {
      // Update all the copies of this backing_store handle.
      *dst_elms.location() =
          BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index))
              ->ptr();
      receiver->set_elements(*dst_elms);
      // Adjust the hole offset as the array has been shrunk.
      hole_end -= src_index;
      DCHECK_LE(hole_start, backing_store->length());
      DCHECK_LE(hole_end, backing_store->length());
    } else if (len != 0) {
      WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind);
      dst_elms->MoveElements(heap, dst_index, src_index, len, mode);
    }
    if (hole_start != hole_end) {
      dst_elms->FillWithHoles(hole_start, hole_end);
    }
  }

Ich möchte auch darauf hinweisen, dass v8 ein unterschiedliches Konzept hat, element kindsje nachdem, was das Array enthält. Dies kann auch die Leistung beeinträchtigen.

Es ist schwer zu sagen, wie hoch die Leistung ist, da es ehrlich gesagt davon abhängt, welche Arten von Elementen übergeben werden, wie viele Löcher sich im Array befinden usw. Wenn ich dies genauer durchforste, kann ich vielleicht eine endgültige Antwort geben, aber im Allgemeinen gehe ich davon aus Da unshiftmehr Platz im Array reserviert werden muss, können Sie im Allgemeinen davon ausgehen, dass es O (N) ist (wird abhängig von der Anzahl der Elemente linear skaliert), aber jemand korrigiert mich bitte, wenn ich falsch liege.

aug
quelle
3

imho es hängt von der Javascript-Engine ab ... wenn es eine verknüpfte Liste verwendet, sollte das Verschieben ziemlich billig sein ...

Er
quelle
13
Perf auf den meisten Websites würde durch den Boden gehen, wenn Array mit einer verknüpften Liste implementiert würde ...
Steven Lu
1
Recht. Für einen nicht verschobenen Betrieb mit einer verknüpften Liste erhalten Sie jedoch eine O (1) -Komplexität. Es kommt also auf den Anwendungsfall an. Die meisten Websites würden Push-Over-Shift jedoch lieber optimieren.
Harry Moreno
Denken Sie, dass keine Site das Array-Konstrukt optimieren würde (indem sie den zugrunde liegenden abstrakten Datentyp ändert)? Es hängt also völlig von der internen Struktur, den Optimierungen und den zugrunde liegenden Datentypen von JS-VMs ab.
TheHe
3

Eine Möglichkeit, Arrays sowohl mit schnellem Verschieben als auch mit Push zu implementieren, besteht darin, Ihre Daten einfach in die Mitte Ihres C-Level-Arrays zu stellen. So macht es Perl, IIRC.

Eine andere Möglichkeit besteht darin, zwei separate C-Level-Arrays zu verwenden, sodass Push-Anhänge an einen von ihnen und Unshift-Anhänge an den anderen angehängt werden. Es gibt keinen wirklichen Vorteil für diesen Ansatz gegenüber dem vorherigen, den ich kenne.

Unabhängig davon, wie es implementiert ist, dauert ein Push- oder Un-Shift-Vorgang O (1), wenn das interne Array auf C-Ebene über genügend freien Speicher verfügt. Andernfalls muss bei einer Neuzuweisung mindestens O (N) Zeit zum Kopieren der alten Daten benötigt werden in den neuen Speicherblock.

BenGoldberg
quelle