315

Nサイズが(where )の配列があると仮定すると、N > 0O(N + 1) ステップを必要としない配列の先頭に追加するより効率的な方法はありますか?

コードでは、本質的に、私が現在行っていることは

function prependArray(value, oldArray) {
  var newArray = new Array(value);

  for(var i = 0; i < oldArray.length; ++i) {
    newArray.push(oldArray[i]);
  }

  return newArray;
}
4

10 に答える 10

558

big-O に関してはより効率的かどうかはわかりませんが、確かにメソッドを使用するunshift方がより簡潔です。

var a = [1, 2, 3, 4];
a.unshift(0);
// => [0, 1, 2, 3, 4]
console.log({a});

[編集]

このjsPerf ベンチマークは、配列をインプレースで変更しても問題がなければ、unshift big-O のパフォーマンスが異なる可能性があるにもかかわらず、少なくともいくつかのブラウザーでかなり高速であることを示しています。元の配列を本当に変更できない場合は、以下のスニペットのようなことを行いますが、ソリューションよりもかなり高速ではないようです。

a.slice().unshift(0); // Use "slice" to avoid mutating "a".

[編集2]

完全を期すために、OPの例の代わりに次の関数を使用prependArray(...)して、Arrayunshift(...)メソッドを利用できます。

function prepend(value, array) {
  var newArray = array.slice();
  newArray.unshift(value);
  return newArray;
}

var x = [1, 2, 3];
var y = prepend(0, x);
// x => [1, 2, 3];
// y => [0, 1, 2, 3];
console.log({ x, y });

于 2011-06-01T02:51:14.753 に答える
91

ES6 では、スプレッド演算子を使用して、新しい要素を元の要素の前に挿入した新しい配列を作成できるようになりました。

// Prepend a single item.
const a = [1, 2, 3];
console.log([0, ...a]);

// Prepend an array.
const a = [2, 3];
const b = [0, 1];
console.log([...b, ...a]);

2018 年 8 月 17 日更新: パフォーマンス

この回答は、より記憶に残り、簡潔であると思われる代替構文を提示することを意図していました。いくつかのベンチマーク (この他の回答を参照) によると、この構文は大幅に遅いことに注意してください。これらの操作の多くをループで実行しない限り、これはおそらく問題になりません。

于 2016-07-18T12:26:38.467 に答える
53

配列を別の配列の前に追加する場合は、単に を使用する方が効率的concatです。そう：

const newArray = [1, 2, 3].concat([4, 5]);
newArray; // [1, 2, 3, 4, 5]

しかし、これは oldArray のサイズではまだ O(N) になります。それでも、手動で oldArray を反復処理するよりも効率的です。また、詳細によっては、多くの値を先頭に追加する場合は、それぞれを個別に先頭に追加するのではなく、最初にそれらを配列に入れてから最後に oldArray を連結する方がよいため、役立つ場合があります。

配列は最初の要素が固定位置にある連続したメモリに格納されるため、oldArray のサイズで O(N) よりも優れた方法はありません。最初の要素の前に挿入したい場合は、他のすべての要素を移動する必要があります。これを回避する方法が必要な場合は、@GWW が言ったことを実行し、リンクされたリストまたは別のデータ構造を使用してください。

于 2011-06-01T02:54:52.473 に答える
33

配列 (配列 a2 を持つ a1) を先頭に追加したい場合は、次のように使用できます。

var a1 = [1, 2];
var a2 = [3, 4];
Array.prototype.unshift.apply(a1, a2);
console.log(a1);
// => [3, 4, 1, 2]
于 2014-12-25T13:30:22.070 に答える
6

古い配列を保存する必要がある場合は、古い配列をスライスし、新しい値をスライスの先頭にシフト解除します。

var oldA=[4,5,6];
newA=oldA.slice(0);
newA.unshift(1,2,3)

oldA+'\n'+newA

/*  returned value:
4,5,6
1,2,3,4,5,6
*/
于 2011-06-01T05:30:24.487 に答える
5

プリペンドのさまざまな方法のいくつかの新しいテストがあります。小さな配列 (<1000 要素) の場合、リーダーはプッシュ メソッドと組み合わせたサイクル用です。巨大な配列の場合、Unshift メソッドがリーダーになります。

ただし、この状況は Chrome ブラウザーでのみ実際に発生します。Firefox では、unshift は素晴らしい最適化を備えており、すべてのケースでより高速です。

ES6 の拡散は、すべてのブラウザーで 100 倍以上遅くなります。

https://jsbench.me/cgjfc79bgx/1

于 2018-03-29T08:02:49.377 に答える
3

特別な方法があります：

a.unshift(value);

しかし、配列の先頭に複数の要素を追加したい場合は、次のような方法を使用する方が高速です。

var a = [1, 2, 3],
    b = [4, 5];

function prependArray(a, b) {
    var args = b;
    args.unshift(0);
    args.unshift(0);
    Array.prototype.splice.apply(a, args);
}

prependArray(a, b);
console.log(a); // -> [4, 5, 1, 2, 3]
于 2011-06-01T02:54:29.260 に答える
2

インプレースで先頭に追加する例:

var A = [7,8,9]
var B = [1,2,3]

A.unshift(...B)

console.log(A) // [1,2,3,7,8,9]

于 2019-01-16T06:37:38.880 に答える
2

不変の方法では、これがおそらく最良の方法です。

const x = 1
const list = [2, 3, 4]
const newList = [x].concat(list) // [1, 2, 3, 4]

于 2021-04-29T11:59:54.503 に答える