Il modo più efficace per anteporre un valore a un array

Supponendo che io abbia una matrice che ha una dimensione di N (dove N > 0 ), c’è un modo più efficiente di prepending dell’array che non richiederebbe i passi O (N + 1)?

Nel codice, essenzialmente, quello che sto facendo attualmente è

 function prependArray(value, oldArray) { var newArray = new Array(value); for(var i = 0; i < oldArray.length; ++i) { newArray.push(oldArray[i]); } return newArray; } 

Non sono sicuro che sia più efficiente in termini di big-O, ma sicuramente usare il metodo di unshift è più conciso:

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

[Modificare]

Questo benchmark di jsPerf mostra che unshift è decentemente più veloce in almeno un paio di browser, a prescindere dalle possibili prestazioni di big-O, se si sta bene modificando l’array sul posto. Se davvero non riesci a mutare la matrice originale, faresti qualcosa come il frammento di sotto, che non sembra essere sensibilmente più veloce della tua soluzione:

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

[Modifica 2]

Per completezza, è ansible utilizzare la seguente funzione al posto dell’esempio prependArray(...) di OP prependArray(...) per sfruttare il unshift(...) Array unshift(...) :

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

Se si antepone un array alla parte anteriore di un altro array, è più efficiente utilizzare solo concat . Così:

 var newArray = values.concat(oldArray); 

Ma questo sarà ancora O (N) nella dimensione di oldArray. Eppure, è più efficiente di iterare manualmente su oldArray. Inoltre, a seconda dei dettagli, può esserti d’aiuto, perché se stai anteponendo molti valori, è meglio metterli prima in un array e poi concatenarli con oldArray alla fine, piuttosto che anteponendoli singolarmente.

Non c’è modo di fare meglio di O (N) nella dimensione di oldArray, perché gli array sono archiviati nella memoria contigua con il primo elemento in una posizione fissa. Se vuoi inserire prima del primo elemento, devi spostare tutti gli altri elementi. Se hai bisogno di un modo per aggirare questo, fai quello che dice @GWW e usa una lista collegata, o una diversa struttura di dati.

Con ES6, ora puoi usare l’ operatore di spread per creare un nuovo array con i tuoi nuovi elementi inseriti prima degli elementi originali.

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

Se si desidera anteporre l’array (a1 con un array a2), è ansible utilizzare quanto segue:

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

f è necessario preservare il vecchio array, suddividere quello vecchio e spostare i nuovi valori all’inizio della sezione.

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

C’è un metodo speciale:

 a.unshift(value); 

Ma se vuoi anteporre più elementi alla matrice, sarebbe più veloce usare un metodo simile:

 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] 

Ho alcuni nuovi test di diversi metodi di prepending. Per i piccoli array (<1000 elems) il leader è per ciclo accoppiato con un metodo push. Per enormi matrici, il metodo Unshift diventa il leader.

Ma questa situazione è effettiva solo per il browser Chrome. In Firefox unshift ha una fantastica ottimizzazione ed è più veloce in tutti i casi.

La diffusione di ES6 è 100 volte più lenta in tutti i browser.

https://jsbench.me/cgjfc79bgx/1