Moyen le plus efficace pour ajouter une valeur à un tableau

268

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;
}
samccone
la source
autant que j'aime les listes liées et les pointeurs, j'ai l'impression qu'il doit y avoir un moyen plus efficace de faire les choses en utilisant des types de données JS natifs
samccone
@samccone: Ouais méprisez mon commentaire désolé, je pensais que vous aviez dit Java: P
GWW
3
Java, JavaScript, C ou Python, peu importe le langage: le compromis complexité entre tableaux et listes liées est le même. Les listes liées sont probablement assez lourdes dans JS car il n'y a pas de classe intégrée pour elles (contrairement à Java), mais si ce que vous voulez vraiment c'est le temps d'insertion O (1), alors vous voulez une liste liée.
mgiuca
1
Faut-il le cloner?
Ryan Florence
1
S'il est nécessaire de le cloner, alors unshift est inapproprié, car il mute le tableau d'origine et ne crée pas de copie.
mgiuca

Réponses:

493

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];
maerics
la source
190
Qui a décidé d'appeler prepend" unshift"?
Scott Stafford
12
@ScottStafford unshiftsemble plus approprié pour une telle opération de tableau (il déplace les éléments ... plus ou moins physiquement). prependserait plus approprié pour les listes liées, où vous ajoutez littéralement des éléments.
CamilB du
12
unshift est la fonction complémentaire de shift. L'appeler "pré-ajouter" serait un choix étrange. Unshift est de déplacer comme pousser est de faire éclater.
Sir Robert
9
Un seul problème avec cette solution. Unshift () ne retourne pas sa longueur , et non le tableau comme dans cette réponse? w3schools.com/jsref/jsref_unshift.asp
iDVB
4
pushet les unshiftdeux contiennent u, tandis que popet shiftn'en ont pas.
Qian Chen
70

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.

Frank Tan
la source
4
Cela devrait être voté à partir de 2017. C'est concis. En utilisant spread, il redonne le nouveau flux, qui peut être utile pour enchaîner sur d'autres modifications. C'est aussi pur (ce qui signifie que a et b ne sont pas affectés)
Simon
Vous n'avez pas mentionné le temps pris par rapport àunshift
Shashank Vivek
Merci @ShashankVivek. Je voulais que cette réponse présente une syntaxe alternative que je pense être plus mémorable et concise. Je mettrai à jour.
Frank Tan
@FrankTan: Cheers :) +1
Shashank Vivek
46

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.

mgiuca
la source
2
Oh oui, j'ai oublié unshift. Mais notez que a) qui mute oldArray alors concatque non (donc celui qui vous convient le mieux dépend de la situation), et b) il n'insère qu'un élément.
mgiuca
1
Wow, c'est beaucoup plus lent. Eh bien, comme je l'ai dit, il fait une copie du tableau (et crée également un nouveau tableau [0]), tandis qu'unshift le mute en place. Mais les deux devraient être O (N). Acclamations également pour le lien vers ce site - semble très pratique.
mgiuca
2
son bon pour oneliner, car concat renvoie le tableau, et unshift renvoie la nouvelle longueur
Z. Khullah
32

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]
uroslates
la source
6

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
*/
kennebec
la source
4

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

John Klimov
la source
Très bonne réponse! Mais pour vous assurer de ne pas en perdre une partie, vous pouvez reproduire vos cas de test ici (peut-être avec quelques exemples de résultats d'exécution) au cas où, par exemple, jsbench disparaîtrait.
ruffin
3

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]
bjornd
la source
2
Non ... unshift ajoutera un tableau comme premier argument: var a = [4, 5]; a.unshift ([1,2,3]); console.log (a); // -> [[4, 5], 1, 2, 3]
bjornd
4
Vous avez raison! Vous devez utiliserArray.prototype.unshift.apply(a,b);
David
1

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]

Miguel Mota
la source
1

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.

rehman_00001
la source