Javascript: Quel est l'algorithmique de la performance de "splice'?
Qui est, serais-je mieux d'utiliser une sorte d'arbre ou d'ignorer la structure de données de liste, si j'ai besoin d'être à l'appel de cette fonction de beaucoup pour le tableau individuels insertions?
- Tester! C'est la meilleure façon de répondre à cette question...
- Ce qui est un bon moyen de tester cela?
- Si JavaScript est tableaux sont vraiment des tableaux, c'est O(n).
- Dans ce cas, je serais mieux avec une autre structure de données, droit?
- IE utilisé un algorithme de hachage pour les tableaux, si je me souviens bien.
- En cas
splice
supprime ou ajoute des éléments, vous aurez besoin de créer un nouveau tableau avec la nouvelle longueur et de la copier au moins tous les éléments avant la suppression/insertion de la position et de tous les éléments à partir de cette position, qu'il n'est O(n). Seuls les en-lieu de remplacement prendra juste O(1) pour chaque élément remplacé. - Ouais, je suppose que ça a du sens.
- JavaScript tableaux ne sont pas vraiment des tableaux (ils sont juste des cartes avec des clés de chaîne qui sont [principalement] tout-numérique et de la magie
length
de la propriété), il est donc totalement dépendant de l'implémentation. - Ils ont les clés devront encore être modifié individuellement à partir de l'élément inséré, bien. Toujours O(n) je crois.
Vous devez vous connecter pour publier un commentaire.
Vous pourriez envisager si vous souhaitez utiliser un objet à la place; tous les objets JavaScript (y compris
Array
instances) sont (très optimisé) ensembles de paires clé/valeur en option avec un prototype de mise en œuvre devrait (notez que je ne dis pas "ne") ont un rendement raisonnables algorithme de hachage. (Mise à jour: C'était en 2010. Ici à 2018, les objets sont très optimisé sur tous les principaux moteurs JavaScript.)A côté de cela, la performance de
splice
va varier d'un beaucoup entre les différentes applications (par exemple, les fournisseurs). C'est une des raisons pourquoi "ne pas optimiser prématurément" est encore plus de conseils appropriés pour des applications JavaScript qui s'exécute en plusieurs implémentations de fournisseur (applications web, par exemple) qu'il est de même pour la programmation normale. Gardez votre code bien modulaires et régler les problèmes de rendement, si et quand ils se produisent.Array
(qui en JavaScript est, après tout, juste une carte avec un ordre défini et une magielength
de la propriété).splice
, mais c'est unArray
avecsplice
une bonne structure de données pour une telle tâche? Si non, quelles autres JS structure de données peut être adapté pour cela?splice
solution. Mais si des modifications sont plus sensibles à la vitesse de recherches, vous pourriez voulez une liste chaînée (JavaScript n'a pas intégré, mais ils ne sont pas difficile à faire). Habituellement, les recherches de dominer, donc pour un ensemble ordonné, un tableau avec dessplice
de sens.x
les coordonnées qui je veux garder dans l'ordre de gauche (en bas àx
valeur) à droite (plusx
valeur). Ensuite, j'ai besoin de mettre à jour fréquemment cette liste et ajouter un peu dex
entre ceux déjà existant. J'ai maintenant, je peux trouver facilement l'index où le nouveaux
doit être positionné à l'aide d'une recherche binaire sur le tableau, mais alors quand il s'agit d'ajouter l'élément entre les deux, je voudrais vous souhaitez le faire d'une certaine manière, sans ré-indexation du tableau à partir de ce point jusqu'à la fin de lax
valeurs qui viennent après le nouveau ajouté un... Pourriez-vous s'il vous plaît aviser comment dois-je m'adresser?:-)
)!Voici une bonne règle empirique, basée sur des tests effectués dans Chrome, Safari et Firefox: Épissage une valeur unique dans le milieu d'un tableau est à peu près la moitié aussi vite que de pousser/passer d'une valeur à l'une des extrémités du tableau. (Remarque: testé Uniquement sur un tableau de taille 10 000 habitants.)
http://jsperf.com/splicing-a-single-value
C'est assez rapide. Donc, il est peu probable que vous avez besoin d'aller aussi loin que de mettre en œuvre une autre structure de données afin d'en extraire plus de performance.
Mise à jour: Que l'eBusiness points dans les commentaires ci-dessous, le test effectue une coûteuse opération de copie avec chaque
splice
,push
, etshift
, ce qui signifie qu'il sous-estime la différence de performance. Voici une version révisée du test qui évite que le tableau de la copie, de sorte qu'il devrait être beaucoup plus précis: http://jsperf.com/splicing-a-single-value/19getArr()
au sein de l'épreuve, dansgetArr()
vous exécutezarr.slice(0)
, qui est un raccourci pour la duplication d'un tableau. Si votre test est de faire une duplication complète de 10000 élément de tableau et une seule opération sur un tableau.splice
etpush
/shift
. Je vais modifier ma réponse en conséquence.Déplacer seule valeur
JS:
Préfèrent
shift
/pop
àsplice
en cas de fonctionnement à tête ou en queue de tableau:https://jsperf.com/1m-array-operations