Big O des tableaux JavaScript

Les tableaux en JavaScript sont très faciles à modifier en ajoutant et en supprimant des éléments. Cela masque quelque peu le fait que la plupart des tableaux de langues sont de taille fixe et nécessitent des opérations complexes de redimensionnement. Il semble que JavaScript facilite l'écriture de code de tableau peu performant. Cela conduit à la question:

Quelles performances (en termes de grande complexité en temps O) puis-je attendre des implémentations JavaScript en ce qui concerne les performances des baies?

Je suppose que toutes les implémentations JavaScript raisonnables ont au plus les grands O suivants.

• Accès - O (1)
• Ajout - O (n)
• Prepending - O (n)
• Insertion - O (n)
• Suppression - O (n)
• Échange - O (1)

JavaScript vous permet de pré-remplir un tableau à une certaine taille, en utilisant la new Array(length)syntaxe. (Question bonus: crée un tableau de cette manière O (1) ou O (n)) Cela ressemble plus à un tableau conventionnel, et s'il est utilisé comme un tableau pré-dimensionné, peut permettre l'ajout de O (1). Si une logique de tampon circulaire est ajoutée, vous pouvez obtenir le préfixe O (1). Si un tableau en expansion dynamique est utilisé, O (log n) sera le cas moyen pour les deux.

Puis-je espérer de meilleures performances pour certaines choses que mes hypothèses ici? Je ne m'attends pas à ce que quoi que ce soit soit décrit dans les spécifications, mais dans la pratique, il se peut que toutes les principales implémentations utilisent des tableaux optimisés dans les coulisses. Existe-t-il des baies à expansion dynamique ou d'autres algorithmes améliorant les performances?

PS

La raison pour laquelle je me demande cela est que je recherche des algorithmes de tri, dont la plupart semblent supposer que l'ajout et la suppression sont des opérations O (1) lors de la description de leur grand O global.

_{REMARQUE: Bien que cette réponse soit correcte en 2012, les moteurs utilisent aujourd'hui des représentations internes très différentes pour les objets et les tableaux. Cette réponse peut être vraie ou non.}

Contrairement à la plupart des langages, qui implémentent des tableaux avec, enfin, des tableaux, en Javascript, les tableaux sont des objets et les valeurs sont stockées dans une table de hachage, tout comme les valeurs d'objet normales. En tant que tel:

• Accès - O (1)
• Ajout - Amorti O (1) (parfois le redimensionnement de la table de hachage est nécessaire; généralement, seule l'insertion est requise)
• Prepending - O (n) via unshift, car il nécessite de réaffecter tous les index
• Insertion - Amorti O (1) si la valeur n'existe pas. O (n) si vous souhaitez déplacer les valeurs existantes (par exemple, en utilisant splice).
• Suppression - Amorti O (1) pour supprimer une valeur, O (n) si vous souhaitez réaffecter des indices via splice.
• Échange - O (1)

En général, la définition ou la désactivation d'une clé dans un dict est amortie O (1), et il en va de même pour les tableaux, quel que soit l'index. Toute opération qui nécessite de renuméroter des valeurs existantes est O (n) simplement parce que vous devez mettre à jour toutes les valeurs affectées.

garantie

Il n'y a aucune garantie de complexité temporelle spécifiée pour toute opération de baie. Le fonctionnement des baies dépend de la structure de données sous-jacente choisie par le moteur. Les moteurs peuvent également avoir des représentations différentes et basculer entre elles en fonction de certaines heuristiques. La taille initiale du tableau peut ou non être une telle heuristique.

réalité

Par exemple, V8 utilise (à partir d'aujourd'hui) à la fois des tables de hachage et des listes de tableaux pour représenter les tableaux. Il a également diverses représentations différentes pour les objets, de sorte que les tableaux et les objets ne peuvent pas être comparés. Par conséquent, l'accès au tableau est toujours meilleur que O (n), et peut même être aussi rapide qu'un accès au tableau C ++. L'ajout est O (1), sauf si vous atteignez la taille de la structure de données et qu'il doit être mis à l'échelle (qui est O (n)). La prépension est pire. La suppression peut être encore plus pire si vous faites quelque chose comme delete array[index](ne faites pas!), Car cela pourrait forcer le moteur à changer sa représentation.

Conseil

Utilisez des tableaux pour les structures de données numériques. C'est à cela qu'ils sont destinés. C'est pour cela que les moteurs vont les optimiser. Évitez les tableaux clairsemés (ou si vous devez le faire, attendez-vous à de moins bonnes performances). Évitez les tableaux avec des types de données mixtes (car cela rend les représentations internes plus complexes ).

Si vous voulez vraiment optimiser pour un certain moteur (et une version), vérifiez son code source pour la réponse absolue.