Tableau dynamique - Dynamic array

Plusieurs valeurs sont insérées à la fin d'un tableau dynamique en utilisant l'expansion géométrique. Les cellules grises indiquent l'espace réservé à l'expansion. La plupart des insertions sont rapides (temps constant), tandis que certaines sont lentes en raison du besoin de réallocation (temps Θ( n ), étiqueté avec des tortues). La taille logique et la capacité de la baie finale sont affichées.

En informatique , un réseau de dynamique , tableau Growable , tableau redimensionnable , table dynamique , tableau modifiable ou liste de réseau est un accès aléatoire , la liste de taille variable structure de données qui permet aux éléments d'être ajoutés ou supprimés. Il est fourni avec des bibliothèques standard dans de nombreux langages de programmation courants modernes. Les baies dynamiques dépassent une limite de baies statiques , qui ont une capacité fixe qui doit être spécifiée lors de l'allocation.

Un tableau dynamique n'est pas la même chose qu'un tableau alloué dynamiquement , qui est un tableau dont la taille est fixe lorsque le tableau est alloué, bien qu'un tableau dynamique puisse utiliser un tel tableau de taille fixe comme back-end.

Baies dynamiques de taille limitée et capacité

Un tableau dynamique simple peut être construit en attribuant un tableau de taille fixe, généralement plus grand que le nombre d'éléments immédiatement requis. 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 du tableau sous-jacent sont réservées ou inutilisées. Des éléments peuvent être ajoutés à la fin d'un tableau dynamique en temps constant en utilisant l'espace réservé, jusqu'à ce que cet espace soit complètement consommé. Lorsque tout l'espace est consommé et qu'un élément supplémentaire doit être ajouté, le tableau de taille fixe sous-jacent doit être augmenté en taille. En règle générale, le redimensionnement est coûteux car il implique l'allocation d'un nouveau tableau sous-jacent et la copie de chaque élément du tableau d'origine. Les éléments peuvent être supprimés de la fin d'un tableau dynamique en temps constant, car aucun redimensionnement n'est requis. Le nombre d'éléments utilisés par le contenu du tableau dynamique correspond à sa taille logique ou taille , tandis que la taille du tableau sous-jacent est appelée capacité ou taille physique du tableau dynamique , qui est la taille maximale possible sans déplacer les données.

Un tableau de taille fixe suffira dans les applications où la taille logique maximale est fixe (par exemple par spécification), ou peut être calculée avant que le tableau ne soit alloué. Un tableau dynamique peut être préféré si :

  • la taille logique maximale est inconnue, ou difficile à calculer, avant que le tableau ne soit alloué
  • 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'une baie dynamique n'affecte pas de manière significative les performances ou la réactivité

Expansion géométrique et coût amorti

Pour éviter d'avoir à redimensionner plusieurs fois, les tableaux dynamiques redimensionnent beaucoup, par exemple en doublant de taille, et utilisent l'espace réservé pour une expansion future. L'opération d'ajout d'un élément à la fin peut fonctionner comme suit : 

function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // resize a to twice its current capacity:
        a.capacity ← a.capacity * 2 
        // (copy the contents to the new memory location here)
    a[a.size] ← e
    a.size ← a.size + 1

Au fur et à mesure que n éléments sont insérés, les capacités forment une progression géométrique . L'expansion du tableau selon une proportion constante a garantit que l'insertion de n éléments prend un temps global de O ( n ) , ce qui signifie que chaque insertion prend un temps constant amorti . De nombreuses baies dynamiques désallouent également une partie du stockage sous-jacent si sa taille tombe en dessous d'un certain seuil, tel que 30 % de la capacité. Ce seuil doit être strictement inférieur à 1/ a afin de fournir une hystérésis (fournir une bande stable pour éviter une croissance et un rétrécissement répétés) et supporter des séquences mixtes d'insertions et de retraits avec un coût constant amorti.

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

Facteur de croissance

Le facteur de croissance du tableau dynamique dépend de plusieurs facteurs, notamment un compromis espace-temps et des algorithmes utilisés dans l'allocateur de mémoire lui-même. Pour le facteur de croissance a , le temps moyen par opération d'insertion est d' environ a /( a -1 ), tandis que le nombre de cellules gaspillées est borné ci-dessus par ( a -1 ) n . Si allocateur de mémoire utilise une première forme allocation algorithme, puis facteur de croissance des valeurs telles que un = 2 peut provoquer une expansion de tableau dynamique à court de mémoire , même si une quantité importante de mémoire peut être encore disponible. Il y a eu diverses discussions sur les valeurs idéales des facteurs de croissance, y compris des propositions pour le nombre d' or ainsi que la valeur 1,5. Cependant, de nombreux manuels utilisent a  = 2 à des fins de simplicité et d'analyse.

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

Mise en œuvre Facteur de croissance ( a )
Liste de tableaux Java 1,5 (3/2)
Python PyListObject ~1.125 (n + n >> 3)
Microsoft Visual C++ 2013 1,5 (3/2)
G++ 5.2.0 2
Clang 3.6 2
Facebook folie/FBVector 1,5 (3/2)
Rouille Vec 2
Allez les tranches entre 1,25 et 2

Performance

Comparaison des structures de données de liste
Coup d'oeil Muter (insérer ou supprimer) à … Espace excédentaire,
moyen
Début Finir Milieu
Liste liée ( n ) (1) (1), élément terminal connu ;
( n ), élément final inconnu 		Heure de
pointe + Θ(1) 		( n )
Déployer (1) N / A N / A N / A 0
Tableau dynamique (1) ( n ) (1) amorti ( n ) ( n )
Arbre équilibré (log n) (log n) (log n ) (log n ) ( n )
Liste à accès aléatoire (log n) (1) N / A N / A ( n )
Arborescence du tableau haché (1) ( n ) (1) amorti ( n ) (√ n )

Le tableau dynamique a des performances similaires à un tableau, avec l'ajout de nouvelles opérations pour ajouter et supprimer des éléments :

  • Obtenir ou définir la valeur à un index particulier (temps constant)
  • Itération sur les éléments dans l'ordre (temps linéaire, bonne performance du cache)
  • Insertion ou suppression d'un élément au milieu du tableau (temps linéaire)
  • Insertion ou suppression d'un élément en fin de tableau (temps d'amortissement constant)

Les baies dynamiques bénéficient de nombreux avantages des baies, notamment une bonne localisation de référence et une bonne utilisation du cache de données , la compacité (faible utilisation de la mémoire) et l'accès aléatoire . Ils n'ont généralement qu'un petit surcoût fixe supplémentaire pour stocker des informations sur la taille et la capacité. Cela fait des tableaux dynamiques un outil attrayant pour créer des structures de données compatibles avec le cache . Cependant, dans des langages comme Python ou Java qui appliquent la sémantique de référence, le tableau dynamique ne stockera généralement pas les données réelles, mais stockera plutôt des références aux données qui résident dans d'autres zones de la mémoire. Dans ce cas, l'accès séquentiel aux éléments du tableau impliquera en fait l'accès à plusieurs zones de mémoire non contiguës, de sorte que les nombreux avantages de la convivialité du cache de cette structure de données sont perdus.

Par rapport aux listes chaînées , les tableaux dynamiques ont une indexation plus rapide (temps constant par rapport au temps linéaire) et une itération généralement plus rapide en raison de l'amélioration de la localité de référence ; cependant, les tableaux dynamiques nécessitent un temps linéaire pour être insérés ou supprimés à un emplacement arbitraire, car tous les éléments suivants doivent être déplacés, tandis que les listes chaînées peuvent le faire en temps constant. Cet inconvénient est atténué par le tampon d' espacement et les variantes vectorielles à plusieurs niveaux décrites sous Variantes ci-dessous. De plus, dans une région de mémoire très fragmentée , il peut être coûteux ou impossible de trouver un espace contigu pour un grand tableau dynamique, alors que les listes chaînées n'exigent pas que toute la structure de données soit stockée 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 de non- stockage contigu et frais généraux de traversée/manipulation d'arbre.

Variantes

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

Goodrich a présenté un algorithme de tableau dynamique appelé vecteurs à plusieurs niveaux qui fournit des performances O ( n 1/ k ) pour les insertions et suppressions de n'importe où dans le tableau, et O ( k ) get et set, où k 2 est un paramètre constant.

L'arbre de tableau haché (HAT) est un algorithme de tableau dynamique publié par Sitarski en 1996. L'arbre de tableau haché gaspille l'ordre n 1/2 d'espace de stockage, où n est le nombre d'éléments dans le tableau. L'algorithme a des performances amorties O (1) lors de l'ajout d'une série d'objets à la fin d'un arbre de tableau haché.

Dans un article de 1999, Brodnik et al. décrivent une structure de données de tableau dynamique à plusieurs niveaux, qui ne gaspille que n 1/2 d' espace pour n éléments à tout moment, et ils prouvent une limite inférieure montrant que tout tableau dynamique doit perdre autant d'espace si les opérations doivent rester amorties à temps constant . De plus, ils présentent une variante où l'augmentation et la réduction du tampon ont non seulement amorti mais le pire des cas constants.

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

Support linguistique

C ++ 's std::vectoret la rouille de std::vec::Vecsont mises en œuvre de tableaux dynamiques, comme le sont les ArrayListclasses fournies avec le Java API et le .NET Framework .

La List<>classe générique fournie avec la version 2.0 du .NET Framework est également implémentée avec des tableaux dynamiques. Smalltalk s » OrderedCollectionest une matrice de dynamique avec démarrage dynamique et à la fin d'indice, ce qui rend le retrait du premier élément également O (1).

L' listimplémentation du type de données de Python est un tableau dynamique.

Delphi et D implémentent des tableaux dynamiques au cœur du langage.

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

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

Plusieurs frameworks multiplateformes fournissent des implémentations de tableaux dynamiques pour C , y compris CFArrayet CFMutableArraydans Core Foundation et GArrayet GPtrArraydans GLib .

Common Lisp fournit un support rudimentaire pour les vecteurs redimensionnables en permettant de configurer le type intégré arraycomme réglable et l'emplacement d'insertion par le pointeur de remplissage .

Les références

  1. ^ a b Voir, par exemple, le code source de la classe java.util.ArrayList d'OpenJDK 6 .
  2. ^ Lambert, Kenneth Alfred (2009), « Taille physique et taille logique » , Principes fondamentaux de Python : des premiers programmes à travers les structures de données , Cengage Learning, p. 510, ISBN 978-1423902188
  3. ^ un b Goodrich, Michael T. ; Tamassia, Roberto (2002), "1.5.2 Analyse d'une implémentation de tableau extensible", Conception d'algorithmes : fondements, analyse et exemples Internet , Wiley, pp. 39-41.
  4. ^ un b Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "17.4 Tableaux dynamiques". Introduction aux algorithmes (2e éd.). MIT Press et McGraw-Hill. p. 416-424. ISBN 0-262-03293-7.
  5. ^ A b c "C ++ vecteur STL: définition, le facteur de croissance, les fonctions membres" . Archivé de l'original le 2015-08-06 . Récupéré le 05-08-2015 .
  6. ^ "facteur de croissance vectorielle de 1,5" . comp.lang.c++.modéré . Groupes Google.
  7. ^ Implémentation d' objets de liste à partir de github.com/python/cpython/, récupéré le 23/03/2020.
  8. ^ Brais, Hadi. "Disséquer le vecteur STL C++ : Partie 3 - Capacité et taille" . Micromystères . Récupéré le 05-08-2015 .
  9. ^ "facebook/folie" . GitHub . Récupéré le 05-08-2015 .
  10. ^ "rouille-lang/rouille" . GitHub . Récupéré le 2020-06-09 .
  11. ^ "golang/go" . GitHub . Récupéré le 2021-09-14 .
  12. ^ Keynote Jour 1 - Bjarne Stroustrup: Style C++11 à GoingNative 2012 sur channel9.msdn.com à partir de la minute 45 ou feuille 44
  13. ^ Chiffrage : pourquoi vous ne devriez jamais, jamais, JAMAIS utiliser à nouveau la liste liée dans votre code sur kjellkod.wordpress.com
  14. ^ Brodnik, Andrej; Carlsson, Svante ; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Rapport technique CS-99-09) (PDF) , Département d'informatique, Université de Waterloo
  15. ^ A b c Chris Okasaki (1995). "Listes à accès aléatoire purement fonctionnelles". Actes de la septième conférence internationale sur les langages de programmation fonctionnels et l'architecture informatique : 86-95. doi : 10.1145/224164.224187 .
  16. ^ Goodrich, Michael T. ; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences" , Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 1663 : 205-216 , doi : 10.1007/3-540 -48447-7_21 , ISBN 978-3-540-66279-2
  17. ^ Sitarski, Edward (septembre 1996), "HATs: Hashed array trees" , Algorithm Alley, Dr. Dobb's Journal , 21 (11)
  18. ^ Brodnik, Andrej; Carlsson, Svante ; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF) (Rapport technique CS-99-09), Département d'informatique, Université de Waterloo
  19. ^ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays , EPFL
  20. ^ Javadoc surArrayList
  21. ^ Classe ArrayList

Liens externes