La complexité de l'exécution JavaScript des fonctions Array

La complexité d'exécution est-elle définie par la norme JS sur les fonctions communes de la Array comme push , pop , shift , slice ou splice ? Esp. Je m'intéresse à supprimer et à insérer des entrées dans des positions aléatoires. Si la complexité n'est pas définie, que puis-je attendre, par exemple dans V8?

(Cette question a été inspirée par cela . De plus, ce benchmark , publié ici , me rend également curieux, mais peut-être que ce sont des phénomènes indépendants.)

(Une question très connexe est ici . Cependant, l'un des commentaires sur la réponse acceptée indique qu'il est faux maintenant. De plus, la réponse acceptée n'a aucune référence pour que la norme la définisse de cette façon.).

La spécification ECMA ne spécifie pas une complexité de délimitation, mais vous pouvez en dériver l'un des algorithmes de la spécification.

push est O (1) , cependant, en pratique, il rencontrera des coûts de copie O (N) aux limites définies par le moteur car le réseau de fentes doit être réaffecté. Ces limites sont généralement logarithmiques.

pop est O (1) avec une contrainte semblable à la push mais la copie O (N) est rarement rencontrée car elle est souvent pliée dans la collecte des ordures (par exemple, un collecteur de copie ne peut copier que la partie utilisée d'un tableau).

shift est au pire O (N), mais il peut, dans des cas particuliers, être mis en œuvre comme O (1) au prix de ralentissement de l'indexation afin que votre kilométrage puisse varier.

slice est O (N) où N est en end - start . Pas une quantité énorme d'opportunité d'optimisation ici sans ralentir considérablement les écritures sur les deux tableaux.

splice est, le pire des cas, O (N) . Il existe des techniques de stockage de tableaux qui divisent N par une constante, mais elles ralentissent considérablement l'indexation. Si un moteur utilise de telles techniques, vous pouvez remarquer des opérations exceptionnellement lentes, puisqu'il bascule entre les techniques de stockage déclenchées par les modifications du modèle d'accès.

L'un que vous n'avez pas mentionné, c'est un sort . C'est, dans le cas moyen, O (N log N) . Cependant, selon l'algorithme choisi par le moteur, vous pouvez obtenir O (N ^ 2) dans certains cas. Par exemple, si le moteur utilise QuickSort (même avec une sortie tardive à InsertionSort), il a des cas N ^ 2 bien connus. Cela pourrait être une source de DoS pour votre application. Si ceci est une préoccupation soit limiter la taille des tableaux que vous trier (peut-être fusionner les sous-arrays) ou sauvetage à HeapSort.

La tranche n'est linéaire que si le nombre est pris est inconnu. Si le nombre de tranches est constant, la tranche est constante, non linéaire.