Cara paling efisien untuk menambahkan nilai ke array

Dengan asumsi saya memiliki sebuah array yang memiliki ukuran N(di mana N > 0), apakah ada cara yang lebih efisien untuk membuat ulang array yang tidak memerlukan langkah-langkah O (N +1)?

Dalam kode, pada dasarnya, apa yang saya lakukan saat ini adalah

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

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

  return newArray;
}

Saya tidak yakin tentang lebih efisien dalam hal big-O tetapi tentu saja menggunakan unshiftmetode ini lebih ringkas:

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

[Sunting]

Benchmark jsPerf ini menunjukkan bahwa unshiftlebih cepat dalam setidaknya beberapa browser, terlepas dari kinerja O besar yang mungkin berbeda jika Anda ok dengan memodifikasi array di tempat. Jika Anda benar-benar tidak dapat mengubah array asli maka Anda akan melakukan sesuatu seperti cuplikan di bawah ini, yang sepertinya tidak jauh lebih cepat daripada solusi Anda:

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

[Sunting 2]

Untuk kelengkapan, fungsi berikut dapat digunakan sebagai ganti contoh OP prependArray(...)untuk memanfaatkan unshift(...)metode Array :

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

var x = [1, 2, 3];
var y = prepend(0, x);
y; // => [0, 1, 2, 3];
x; // => [1, 2, 3];

Dengan ES6, Anda sekarang dapat menggunakan operator spread untuk membuat array baru dengan elemen baru Anda dimasukkan sebelum elemen asli.

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

Pembaruan 2018-08-17: Kinerja

Saya bermaksud jawaban ini untuk menyajikan sintaks alternatif yang saya pikir lebih berkesan dan ringkas. Perlu dicatat bahwa menurut beberapa tolok ukur (lihat jawaban lain ini ), sintaks ini secara signifikan lebih lambat. Ini mungkin tidak akan menjadi masalah kecuali Anda melakukan banyak operasi ini dalam satu lingkaran.

Jika Anda menambahkan sebuah array ke bagian depan array lain, itu lebih efisien untuk digunakan saja concat. Begitu:

var newArray = values.concat(oldArray);

Tapi ini masih akan menjadi O (N) dalam ukuran oldArray. Namun, ini lebih efisien daripada iterasi manual di atas oldArray. Juga, tergantung pada detailnya, ini dapat membantu Anda, karena jika Anda akan menambahkan banyak nilai, lebih baik untuk meletakkannya ke dalam array terlebih dahulu dan kemudian menyelesaikan oldArray di akhir, daripada menambahkan masing-masing secara terpisah.

Tidak ada cara untuk berbuat lebih baik daripada O (N) dalam ukuran oldArray, karena array disimpan dalam memori yang berdekatan dengan elemen pertama dalam posisi tetap. Jika Anda ingin memasukkan sebelum elemen pertama, Anda harus memindahkan semua elemen lainnya. Jika Anda perlu cara lain, lakukan apa yang dikatakan @GWW dan gunakan daftar tertaut, atau struktur data yang berbeda.

Jika Anda ingin menambahkan array (a1 dengan array a2), Anda bisa menggunakan yang berikut ini:

var a1 = [1, 2];
var a2 = [3, 4];
Array.prototype.unshift.apply(a1, a2);
console.log(a1);
// => [3, 4, 1, 2]

Jika Anda perlu mempertahankan array lama, potong yang lama dan lepaskan nilai yang baru ke awal slice.

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
*/

Saya memiliki beberapa tes baru dari berbagai metode prapengisian. Untuk array kecil (<1000 elem) pemimpin adalah untuk siklus ditambah dengan metode dorong. Untuk array besar, metode Unshift menjadi pemimpin.

Tetapi situasi ini sebenarnya hanya untuk browser Chrome. Di Firefox unshift memiliki optimasi yang luar biasa dan lebih cepat dalam semua kasus.

Penyebaran ES6 100 kali lebih lambat di semua browser.

https://jsbench.me/cgjfc79bgx/1

Ada metode khusus:

a.unshift(value);

Tetapi jika Anda ingin menambahkan beberapa elemen ke array, akan lebih cepat menggunakan metode seperti ini:

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]

Contoh untuk menambahkan di tempat:

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

A.unshift(...B)

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

Memanggil unshifthanya mengembalikan panjang array baru. Jadi, untuk menambahkan elemen di awal dan mengembalikan array baru, saya melakukan ini:

let newVal = 'someValue';
let array = ['hello', 'world'];
[ newVal ].concat(array);

atau cukup dengan operator spread:

[ newVal, ...array ]

Dengan cara ini, array asli tetap tidak tersentuh.