자바 스크립트에서 unshift () 대 push ()의 시간 복잡성

자바 스크립트에서 unshift () 대 push ()의 시간 복잡성

---

Javascript에서 unshift () 및 push () 메서드의 차이점이 무엇인지 알고 있지만 시간 복잡성의 차이가 무엇인지 궁금합니다.

배열 끝에 항목을 추가하기 때문에 push () 메서드가 O (1)이라고 가정합니다.하지만 unshift () 메서드는 확실하지 않습니다. 다른 모든 항목을 "이동"해야한다고 가정하기 때문입니다. 기존 요소는 앞으로 O (log n) 또는 O (n)이라고 가정합니다.

---

내가 아는 한 JavaScript 언어 사양은 이러한 함수의 시간 복잡성을 요구하지 않습니다.

O (1) push및 unshift연산 을 사용하여 배열과 유사한 데이터 구조 (O (1) 임의 액세스)를 구현하는 것이 확실히 가능 합니다. C ++ std::deque가 그 예입니다. 따라서 C ++ deques를 사용하여 Javascript 배열을 내부적으로 나타내는 Javascript 구현은 O (1) push및 unshift작업을 갖습니다 .

그러나 이러한 시간 제한을 보장해야하는 경우 다음과 같이 직접 굴려야합니다.

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

---

push ()가 더 빠릅니다.

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

---

imho 그것은 javascript-engine에 의존합니다 ... 연결된 목록을 사용한다면 unshift는 상당히 싸야합니다 ...

---

빠른 언 시프트와 푸시를 모두 사용하여 어레이를 구현하는 한 가지 방법은 단순히 데이터를 C 레벨 어레이의 중간에 배치하는 것입니다. 이것이 perl이하는 방식입니다, IIRC.

이를 수행하는 또 다른 방법은 두 개의 개별 C 레벨 배열을 갖는 것이므로 push는 그중 하나에 추가되고 unshift는 다른 하나에 추가됩니다. 내가 알고있는 이전 접근 방식에 비해이 접근 방식에는 실질적인 이점이 없습니다.

구현 방법에 관계없이 내부 C 레벨 어레이에 충분한 여유 메모리가 있으면 push 또는 unshift가 O (1) 시간이 걸리고, 그렇지 않으면 재 할당이 수행되어야 할 때 이전 데이터를 복사하는 데 최소 O (N) 시간이 걸립니다. 새로운 메모리 블록에.

---

v8 구현에 대해 궁금한 사람들을 위해 여기에 소스가 있습니다. unshift임의의 수의 인수를 취하기 때문에 배열은 모든 인수를 수용하도록 자체적으로 이동합니다.

UnshiftImpl호출 끝 AddArguments로모그래퍼 start_position의 AT_START이에 킥이 else문

  // 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);

그리고 그것을 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);
    }
  }

I also want to call out that v8 has a concept of different element kinds depending what the array contains. This also can affect the performance.

It's hard to actually say what the performance is because truthfully it depends on what types of elements are passed, how many holes are in the array, etc. If I dig through this more, maybe I can give a definitive answer but in general I assume since unshift needs to allocate more space in the array, in general you can kinda assume it's O(N) (will scale linerally depending on the number of elements) but someone please correct me if I'm wrong.

참고URL : https://stackoverflow.com/questions/12250697/time-complexity-of-unshift-vs-push-in-javascript