Moyen le plus efficace pour ajouter une valeur à un tableau

En supposant que j'ai un tableau qui a une taille de N(où N > 0), y a-t-il un moyen plus efficace de pré-ajouter au tableau qui ne nécessiterait pas d'étapes O (N + 1)?

En code, essentiellement, ce que je fais actuellement est

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

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

  return newArray;
}

Je ne suis pas sûr d'être plus efficace en termes de big-O, mais l'utilisation de la unshiftméthode est certainement plus concise:

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

[Éditer]

Ce benchmark jsPerf montre qu'il unshiftest décemment plus rapide dans au moins quelques navigateurs, indépendamment des performances big-O éventuellement différentes si vous êtes d'accord avec la modification du tableau en place. Si vous ne pouvez vraiment pas muter le tableau d'origine, vous feriez quelque chose comme l'extrait ci-dessous, qui ne semble pas être beaucoup plus rapide que votre solution:

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

[Modifier 2]

Pour être complet, la fonction suivante peut être utilisée à la place de l'exemple OP prependArray(...)pour tirer parti de la unshift(...)méthode 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];

Avec ES6, vous pouvez désormais utiliser l' opérateur d'étalement pour créer un nouveau tableau avec vos nouveaux éléments insérés avant les éléments d'origine.

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

Mise à jour 2018-08-17: performances

Je voulais que cette réponse présente une syntaxe alternative que je pense être plus mémorable et concise. Il est à noter que selon certains benchmarks (voir cette autre réponse ), cette syntaxe est nettement plus lente. Cela n'aura probablement aucune importance, sauf si vous effectuez plusieurs de ces opérations en boucle.

Si vous ajoutez un tableau à l'avant d'un autre tableau, il est plus efficace de simplement l'utiliser concat. Alors:

var newArray = values.concat(oldArray);

Mais ce sera toujours O (N) dans la taille de oldArray. Pourtant, il est plus efficace que l'itération manuelle sur oldArray. En outre, selon les détails, cela peut vous aider, car si vous souhaitez ajouter de nombreuses valeurs, il est préférable de les placer d'abord dans un tableau, puis de concatrer oldArray à la fin, plutôt que de les ajouter individuellement.

Il n'y a aucun moyen de faire mieux que O (N) dans la taille de oldArray, car les tableaux sont stockés dans une mémoire contiguë avec le premier élément dans une position fixe. Si vous souhaitez insérer avant le premier élément, vous devez déplacer tous les autres éléments. Si vous avez besoin d'un moyen de contourner cela, faites ce que @GWW a dit et utilisez une liste chaînée ou une structure de données différente.

Si vous souhaitez ajouter un tableau (a1 avec un tableau a2), vous pouvez utiliser ce qui suit:

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

Si vous devez conserver l'ancien tableau, découpez l'ancien et décompressez la ou les nouvelles valeurs au début de la tranche.

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

J'ai de nouveaux tests de différentes méthodes de pré-paiement. Pour les petits réseaux (<1000 elems), le leader est pour le cycle couplé à une méthode push. Pour les tableaux énormes, la méthode Unshift devient le leader.

Mais cette situation n'est réelle que pour le navigateur Chrome. Dans Firefox, unshift a une optimisation impressionnante et est plus rapide dans tous les cas.

La diffusion ES6 est 100 fois plus lente dans tous les navigateurs.

https://jsbench.me/cgjfc79bgx/1

Il existe une méthode spéciale:

a.unshift(value);

Mais si vous souhaitez ajouter plusieurs éléments au tableau, il serait plus rapide d'utiliser une telle méthode:

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]

Exemple de pré-paiement sur place:

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

A.unshift(...B)

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

L'appel unshiftrenvoie uniquement la longueur du nouveau tableau. Donc, pour ajouter un élément au début et pour retourner un nouveau tableau, j'ai fait ceci:

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

ou simplement avec l'opérateur spread:

[ newVal, ...array ]

De cette façon, la matrice d'origine reste intacte.