réseau dynamique

En informatique , un tableau dynamique ( ou tableau extensible , ou tableau redimensionnable , est une structure de données de type liste à accès aléatoire et de taille variable, permettant l'ajout ou la suppression d'éléments. Il est fourni par les bibliothèques standard de nombreux langages de programmation modernes courants . Les tableaux dynamiques s'affranchissent de la limitation des tableaux statiques , dont la capacité est fixe et doit être spécifiée lors de leur allocation .

Un tableau dynamique n'est pas la même chose qu'un tableau alloué dynamiquement ou qu'un tableau de longueur variable , qui sont tous deux des tableaux dont la taille est fixée lors de l'allocation du tableau, bien qu'un tableau dynamique puisse utiliser un tel tableau de taille fixe comme backend.

On peut construire un tableau dynamique simple en allouant un tableau de taille fixe, généralement supérieure au nombre d'éléments immédiatement nécessaires. Les éléments du tableau dynamique sont stockés de manière contiguë au début du tableau sous-jacent, et les positions restantes vers la fin de ce dernier sont réservées. On peut ajouter des éléments à la fin d'un tableau dynamique en temps constant en utilisant l'espace réservé, jusqu'à ce que celui-ci soit entièrement utilisé.

Lorsque tout l'espace est utilisé et qu'il faut ajouter un élément, il est nécessaire d'agrandir le tableau sous-jacent de taille fixe. En général, le redimensionnement est une opération coûteuse car elle implique l'allocation d'un nouveau tableau sous-jacent et, éventuellement, la copie de chaque élément du tableau d'origine.

Il est possible de supprimer des éléments à la fin d'un tableau dynamique en temps constant, sans redimensionnement. Le nombre d'éléments utilisés par le contenu du tableau dynamique correspond à sa taille logique ou sa longueur , tandis que la taille du tableau sous-jacent est appelée taille physique ou capacité du tableau dynamique . La capacité représente la taille maximale possible sans déplacement de données.

Un tableau de taille fixe suffit dans les applications où la taille logique maximale est fixée (par exemple, par spécification) ou peut être calculée avant l'allocation du tableau. Un tableau dynamique peut être préférable si :

• La taille logique maximale est inconnue ou difficile à calculer avant l'allocation du tableau.
• On considère qu'une taille logique maximale donnée par une spécification est susceptible de changer
• Le coût amorti du redimensionnement d'un réseau dynamique n'affecte pas significativement les performances ni la réactivité.

Pour éviter les coûts liés à de nombreux redimensionnements, les tableaux dynamiques sont redimensionnés de manière significative, par exemple en doublant leur taille, et utilisent l'espace ainsi libéré pour les extensions futures. L'ajout d'un élément à la fin du tableau peut se dérouler comme suit :

function insertEnd ( dynarray a , element e ) if ( a.size == a.capacity ) // redimensionner a à deux fois sa capacité actuelle : a.capacity ← a.capacity * 2 // ( copier le contenu dans le nouvel emplacement mémoire ici ) a [ a.size ] ← e a.size ← a.size + 1

À mesure que n éléments sont insérés, les capacités suivent une progression géométrique . L'extension du tableau par une proportion constante a garantit que l'insertion de n éléments s'effectue en temps constant O ( n ) , ce qui signifie que chaque insertion a une durée constante amortie (à condition que chaque allocation s'effectue en temps constant O ( 1 )). De nombreux tableaux dynamiques libèrent également une partie de l'espace de stockage sous-jacent si sa taille descend en dessous d'un certain seuil, par exemple 30 % de la capacité. Ce seuil doit être strictement inférieur à 1/ a afin de garantir l'hystérésis (une plage stable évitant les variations répétées de capacité) et de prendre en charge des séquences mixtes d'insertions et de suppressions à coût constant amorti.

Les tableaux dynamiques sont un exemple courant dans l'enseignement de l'analyse amortie .

Le facteur de croissance d'une matrice dynamique dépend de plusieurs facteurs, notamment d'un compromis espace-temps et des algorithmes utilisés par l'allocateur de mémoire. Pour un facteur de croissance a , le temps moyen par opération d'insertion est d'environ a /( a -1), tandis que le nombre de cellules inutilisées est limité à ( a -1) n . Si l'allocateur de mémoire utilise un algorithme d'allocation de type « premier ajustement » , des valeurs de facteur de croissance telles que a = 2 peuvent entraîner une saturation de la mémoire lors de l'expansion de la matrice dynamique, même si une quantité importante de mémoire reste disponible. Diverses discussions ont porté sur les valeurs idéales du facteur de croissance, notamment des propositions concernant le nombre d'or ainsi que la valeur 1,5. Cependant, de nombreux ouvrages utilisent a = 2 par souci de simplicité et à des fins d'analyse.

Vous trouverez ci-dessous les facteurs de croissance utilisés par plusieurs implémentations populaires :

Le tableau dynamique offre des performances similaires à celles d'un tableau, avec en plus de nouvelles opérations pour ajouter et supprimer des éléments :

• Obtention ou définition de la valeur à un index particulier (temps constant)
• Parcourir les éléments dans l'ordre (temps linéaire, bonnes performances du cache)
• Insertion ou suppression d'un élément au milieu du tableau (temps linéaire)
• Insertion ou suppression d'un élément à la fin du tableau (temps amorti constant)

Les tableaux dynamiques bénéficient de nombreux avantages des tableaux classiques, notamment une bonne localité des références et une utilisation efficace du cache , une compacité (faible consommation de mémoire) et un accès aléatoire . Ils n'entraînent généralement qu'une faible surcharge fixe supplémentaire pour le stockage des informations relatives à leur taille et à leur capacité. Cela fait des tableaux dynamiques un outil intéressant pour la conception de structures de données optimisées pour le cache . Cependant, dans les langages comme Python ou Java qui imposent une sémantique de référence, le tableau dynamique ne stocke généralement pas les données elles-mêmes, mais plutôt des références aux données résidant dans d'autres zones de mémoire. Dans ce cas, l'accès séquentiel aux éléments du tableau implique en réalité l'accès à plusieurs zones de mémoire non contiguës, ce qui compromet les nombreux avantages liés à l'optimisation pour le cache de cette structure de données.

Comparativement aux listes chaînées , les tableaux dynamiques offrent un indexage plus rapide (temps constant contre temps linéaire) et généralement une itération plus rapide grâce à une meilleure localité des références. Cependant, l'insertion ou la suppression d'un élément à un emplacement quelconque dans un tableau dynamique nécessite un temps linéaire, car tous les éléments suivants doivent être déplacés, contrairement aux listes chaînées qui effectuent ces opérations en temps constant. Cet inconvénient est atténué par les variantes utilisant un tampon d'espacement et des vecteurs hiérarchisés, décrites dans la section « Variantes » ci-dessous. De plus, dans une zone mémoire fortement fragmentée , il peut être coûteux, voire impossible, de trouver un espace contigu pour un grand tableau dynamique, alors que les listes chaînées n'exigent pas que l'ensemble de la structure de données soit stocké de manière contiguë.

Un arbre équilibré peut stocker une liste tout en fournissant toutes les opérations des tableaux dynamiques et des listes chaînées de manière raisonnablement efficace, mais l'insertion à la fin et l'itération sur la liste sont plus lentes que pour un tableau dynamique, en théorie et en pratique, en raison du stockage non contigu et de la surcharge liée au parcours/à la manipulation de l'arbre.

Les tampons d'espacement sont similaires aux tableaux dynamiques, mais permettent des opérations d'insertion et de suppression efficaces, regroupées à proximité d'un même emplacement arbitraire. Certaines implémentations de deques utilisent des deques de tableaux , qui permettent une insertion/suppression en temps constant amorti aux deux extrémités, au lieu d'une seule.

Goodrich a présenté un algorithme de tableau dynamique appelé vecteurs hiérarchisés qui offre une performance O ( n ^{1/ k} ) pour les insertions et les suppressions de n'importe où dans le tableau, et O ( k ) pour obtenir et définir, où k ≥ 2 est un paramètre constant.

L'algorithme HAT ( Hashed Array Tree ) est un algorithme de tableau dynamique publié par Sitarski en 1996 Il gaspille un espace mémoire de l' ordre de n ^{^1/2, où} n est le nombre d'éléments du tableau. Sa complexité amortie est de O (1) lors de l'ajout d'une série d'objets à la fin d'un arbre de hachage.

Dans un article de 1999 , Brodnik et al. décrivent une structure de données de tableau dynamique hiérarchisé qui n'utilise que n ^{^1/2} espace pour n éléments à tout instant. Ils démontrent une borne inférieure prouvant que tout tableau dynamique doit gaspiller autant d'espace pour que les opérations restent à temps constant amorti. De plus, ils présentent une variante où l'agrandissement et la réduction du tampon ont un temps non seulement amorti, mais également constant dans le pire des cas.

Bagwell (2002) a présenté l'algorithme VList, qui peut être adapté pour implémenter un tableau dynamique.

Les tableaux redimensionnables naïfs — également appelés « la pire implémentation » des tableaux redimensionnables — conservent la taille allouée du tableau exactement suffisante pour toutes les données qu'il contient, par exemple en appelant `realloc` pour chaque élément ajouté. Les tableaux redimensionnables naïfs constituent la manière la plus simple d'implémenter un tableau redimensionnable en C. Ils n'utilisent pas de mémoire inutilement, mais l'ajout d'un élément à la fin du tableau prend toujours un temps Θ( n ). Les tableaux à croissance linéaire pré-allouent (« gaspillent ») un espace Θ(1) à chaque redimensionnement, ce qui les rend beaucoup plus rapides que les tableaux redimensionnables naïfs ; l'ajout d'un élément à la fin du tableau prend toujours un temps Θ( n ), mais avec une constante beaucoup plus petite. Les tableaux redimensionnables naïfs et les tableaux à croissance linéaire peuvent s'avérer utiles lorsqu'une application aux ressources limitées nécessite de nombreux petits tableaux redimensionnables. Ils sont également couramment utilisés comme exemple pédagogique conduisant à des tableaux dynamiques à croissance exponentielle.

Les tableaux dynamiques de C++std::vector et de Ruststd::vec::Vec sont des implémentations de tableaux dynamiques, tout comme ceux de Java java.util.ArrayList et du .NET Framework . System.Collections.ArrayList

La System.Collections.Generic.List<T>classe générique de la version 2.0 du .NET Framework est également implémentée avec des tableaux dynamiques. En Smalltalk , il OrderedCollections'agit d'un tableau dynamique avec des indices de début et de fin dynamiques, ce qui rend la suppression du premier élément également en O(1).

L'implémentation du type de données de Pythonlist est un tableau dynamique dont le modèle de croissance est : 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...

Delphi et D implémentent les tableaux dynamiques au cœur même du langage.

Le package générique d' AdaAda.Containers.Vectors fournit une implémentation de tableau dynamique pour un sous-type donné.

De nombreux langages de script tels que Perl et Ruby offrent des tableaux dynamiques comme type de données primitif intégré .

Plusieurs frameworks multiplateformes fournissent des implémentations de tableaux dynamiques pour C , notamment CFArraydans CFMutableArrayCore Foundation et GArraydans GLib . GPtrArray

Common Lisparray offre une prise en charge rudimentaire des vecteurs redimensionnables en permettant de configurer le type intégré comme ajustable et l'emplacement d'insertion par le pointeur de remplissage .