78

unshift()JavaScriptのメソッドとメソッドの違いはわかりpush()ますが、時間計算量の違いは何ですか？

push()配列の最後にアイテムを追加しているだけなので、メソッドはO（1）だと思いますが、メソッドunshift()についてはよくわかりません。他のすべての既存の要素を前方に「移動」する必要があると思います。それはO（log n）またはO（n）ですか？

4

6 に答える 6

70

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


function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
console.log(foo())

function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
console.log(bar());

アップデート

上記では、配列の順序は考慮されていません。それらを適切に比較したい場合は、プッシュされた配列を逆にする必要があります。10msただし、このスニペットを使用したChromeでは、プッシュしてからリバースする方が〜だけ高速です。

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}`);

于 2014-10-14T21:26:33.667 に答える
27

私の知る限り、JavaScript言語仕様では、これらの関数の時間計算量は義務付けられていません。

pushO（1）と演算を使用して、配列のようなデータ構造（O（1）ランダムアクセス）を実装することは確かに可能unshiftです。C++std::dequeはその一例です。したがって、C ++ dequeを使用してJavascript配列を内部的に表すJavascript実装には、O（1）pushとunshift操作が含まれます。

しかし、そのような期限を保証する必要がある場合は、次のように自分でロールする必要があります。

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

于 2012-09-03T15:40:58.520 に答える
15

v8の実装に興味がある人のために、ここにソースがあります。unshift任意の数の引数を取るため、配列はすべての引数に対応するためにそれ自体をシフトします。

UnshiftImplこのステートメントにそれAddArgumentsを蹴るので呼び出すことになりますstart_positionAT_STARTelse

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

element kindsまた、v8には、アレイに含まれるものによって異なる概念があることを強調したいと思います。これもパフォーマンスに影響を与える可能性があります。

通過する要素の種類や配列内の穴の数などに依存するため、実際にパフォーマンスを判断するのは困難です。これをさらに掘り下げると、決定的な答えが得られるかもしれませんが、一般的には配列により多くのスペースを割り当てる必要があるためunshift、一般的にはO（N）（要素の数に応じて線形にスケーリングされます）と見なすことができますが、間違っている場合は誰かが修正してください。

于 2018-12-04T03:41:30.423 に答える
4

私見それはjavascript-engineに依存します...それがリンクリストを使用する場合、シフト解除はかなり安いはずです...

于 2012-09-03T15:36:22.933 に答える
4

高速アンシフトとプッシュの両方で配列を実装する1つの方法は、データを経営幹部レベルの配列の中央に配置することです。それがperlのやり方です、IIRC。

これを行う別の方法は、2つの別々のCレベルの配列を用意して、一方にプッシュアペンドを、もう一方にアンシフトアペンドを作成することです。私が知っているように、このアプローチには前のアプローチに比べて本当のメリットはありません。

実装方法に関係なく、内部Cレベルアレイに十分なスペアメモリがある場合、プッシュまたはアンシフトにはO（1）時間がかかります。それ以外の場合、再割り当てを行う必要がある場合は、古いデータをコピーするために少なくともO（N）時間かかります。メモリの新しいブロックに。

于 2015-12-02T01:25:57.397 に答える
3

はい、その通りです。のデフォルトの複雑度push()はO（1）で、unshift()O（n）です。unshift()配列にすでに存在するすべての要素をインクリメントする必要があるためです。ただし、push()配列の最後に要素を挿入する必要があるため、配列要素のインデックスを変更する必要はありません。だが、push()メモリの動的割り当てのため、O（n）の複雑さとも言えます。javascriptでは、必要なサイズを指定せずに新しい配列を作成すると、デフォルト値の配列が作成されます。デフォルトのサイズがいっぱいになるまで、プッシュ操作はO（1）複雑さを取ります。ただし、デフォルトサイズがいっぱいの場合、コンパイラはデフォルトメモリの2倍のサイズの新しい連続メモリブロックを作成し、既存の要素を新しく割り当てられたメモリにコピーする必要があります。したがって、要素を1つの連続するメモリブロックから別の連続するメモリブロックに移動するには、O（n）時間かかります。

配列に配置する要素の数がわかっている場合は、要素を挿入するためにO（n）を取得することを回避できます。

  1. 必要なサイズで配列を初期化し、ダミー値で埋めます。 let array = new Array(size).fill(0)
  2. プッシュする要素を繰り返し処理し、インデックスによって値を変更します。
for (let i = 0; i < size; i++) {
  array[i] = i
}

そのため、代わりにpush()、その位置にある要素のインデックスを変更しました。デフォルト値で配列を作成して要素をプッシュするよりも、メモリ効率が高く、複雑さも少なくなります。必要な量のメモリのみを使用しているため、余分なメモリが無駄になることはありません。

于 2021-05-28T03:49:06.470 に答える