Structure de données de tableau - Array data structure

En informatique , une structure de données de type tableau , ou simplement un tableau , est une structure de données constituée d'un ensemble d' éléments ( valeurs ou variables ), chacun identifié par au moins un indice de tableau ou une clé . Un tableau est stocké de telle sorte que la position de chaque élément puisse être calculée à partir de son tuple d' indice par une formule mathématique. Le type de structure de données le plus simple est un tableau linéaire, également appelé tableau à une dimension.

Par exemple, un tableau de 10 variables entières de 32 bits (4 octets), avec les indices 0 à 9, peut être stocké sous forme de 10 mots aux adresses mémoire 2000, 2004, 2008, ..., 2036, (en hexadécimal : 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) de sorte que l'élément d'indice i a pour adresse 2000 + ( i × 4).

L'adresse mémoire du premier élément d'un tableau est appelée première adresse, adresse de fondation ou adresse de base.

Parce que le concept mathématique d'une matrice peut être représenté comme une grille à deux dimensions, les tableaux à deux dimensions sont aussi parfois appelés matrices. Dans certains cas, le terme "vecteur" est utilisé en informatique pour désigner un tableau, bien que les tuples plutôt que les vecteurs soient l'équivalent le plus mathématiquement correct. Les tables sont souvent implémentées sous forme de tableaux, en particulier les tables de recherche ; le mot table est parfois utilisé comme synonyme de tableau .

Les tableaux font partie des structures de données les plus anciennes et les plus importantes et sont utilisés par presque tous les programmes. Ils sont également utilisés pour implémenter de nombreuses autres structures de données, telles que des listes et des chaînes . Ils exploitent efficacement la logique d'adressage des ordinateurs. Dans la plupart des ordinateurs modernes et de nombreux périphériques de stockage externes, la mémoire est un tableau unidimensionnel de mots, dont les indices sont leurs adresses. Les processeurs , en particulier les processeurs vectoriels , sont souvent optimisés pour les opérations de réseau.

Les tableaux sont utiles principalement parce que les indices des éléments peuvent être calculés au moment de l'exécution . Entre autres choses, cette fonctionnalité permet à une seule instruction itérative de traiter arbitrairement de nombreux éléments d'un tableau. Pour cette raison, les éléments d'une structure de données de tableau doivent avoir la même taille et doivent utiliser la même représentation de données. L'ensemble de tuples d'index valides et les adresses des éléments (et donc la formule d'adressage des éléments) sont généralement, mais pas toujours, fixes pendant l'utilisation du tableau.

Le terme tableau est souvent utilisé pour désigner le type de données de tableau , une sorte de type de données fourni par la plupart des langages de programmation de haut niveau qui consiste en une collection de valeurs ou de variables pouvant être sélectionnées par un ou plusieurs indices calculés au moment de l'exécution. Les types de tableau sont souvent implémentés par des structures de tableau ; cependant, dans certains langages, ils peuvent être implémentés par des tables de hachage , des listes chaînées , des arbres de recherche ou d'autres structures de données.

Le terme est également utilisé, notamment dans la description des algorithmes , pour désigner un tableau associatif ou « tableau abstrait », un modèle informatique théorique (un type de données abstrait ou ADT) destiné à capturer les propriétés essentielles des tableaux.

Histoire

Les premiers ordinateurs numériques utilisaient la programmation en langage machine pour configurer et accéder aux structures de tableaux pour les tableaux de données, les calculs vectoriels et matriciels, et à de nombreuses autres fins. John von Neumann a écrit le premier programme de tri par tableau ( tri par fusion ) en 1945, lors de la construction du premier ordinateur à programme stocké . ^{p. 159 L'} indexation des tableaux était à l'origine effectuée par un code auto-modifiant , et plus tard à l'aide de registres d'index et d'adressage indirect . Certains mainframes conçus dans les années 1960, tels que le Burroughs B5000 et ses successeurs, utilisaient la segmentation de la mémoire pour effectuer la vérification des limites d'index dans le matériel.

Les langages d'assemblage n'ont généralement pas de support spécial pour les tableaux, autre que ce que la machine elle-même fournit. Les premiers langages de programmation de haut niveau, dont FORTRAN (1957), Lisp (1958), COBOL (1960) et ALGOL 60 (1960), prenaient en charge les tableaux multidimensionnels, tout comme C (1972). En C++ (1983), des modèles de classe existent pour les tableaux multidimensionnels dont la dimension est fixée à l'exécution ainsi que pour les tableaux flexibles à l'exécution.

Applications

Les tableaux sont utilisés pour implémenter des vecteurs et des matrices mathématiques , ainsi que d'autres types de tableaux rectangulaires. De nombreuses bases de données , petites et grandes, consistent en (ou incluent) des tableaux à une dimension dont les éléments sont des enregistrements .

Les tableaux sont utilisés pour implémenter d'autres structures de données, telles que les listes, les tas , les tables de hachage , les demandes , les files d'attente , les piles , les chaînes et les VLists . Les implémentations basées sur un tableau d'autres structures de données sont souvent simples et économes en espace ( structures de données implicites ), nécessitant peu de surcharge d' espace , mais peuvent avoir une faible complexité d'espace, en particulier lorsqu'elles sont modifiées, par rapport aux structures de données arborescentes (comparez un tableau trié à un arbre de recherche ).

Un ou plusieurs grands tableaux sont parfois utilisés pour émuler l' allocation de mémoire dynamique dans le programme , en particulier l' allocation de pool de mémoire . Historiquement, cela a parfois été le seul moyen d'allouer de la "mémoire dynamique" de manière portable.

Les tableaux peuvent être utilisés pour déterminer le flux de contrôle partiel ou complet dans les programmes, en tant qu'alternative compacte aux IFinstructions multiples (sinon répétitives) . Ils sont connus dans ce contexte sous le nom de tables de contrôle et sont utilisés en conjonction avec un interpréteur spécialement conçu dont le flux de contrôle est modifié en fonction des valeurs contenues dans le tableau. Le tableau peut contenir des pointeurs de sous-programmes (ou des numéros de sous-programmes relatifs sur lesquels les instructions SWITCH peuvent agir ) qui dirigent le chemin de l'exécution.

Identificateur d'élément et formules d'adressage

Lorsque les objets de données sont stockés dans un tableau, les objets individuels sont sélectionnés par un index qui est généralement un entier scalaire non négatif . Les index sont également appelés indices. Un index mappe la valeur du tableau sur un objet stocké.

Il existe trois façons d'indexer les éléments d'un tableau :

0 ( indexation de base zéro )

Le premier élément du tableau est indexé par un indice de 0.

1 ( indexation à base unique )

Le premier élément du tableau est indexé par l'indice de 1.

n ( indexation basée sur n )

L'indice de base d'un tableau peut être choisi librement. Généralement, les langages de programmation permettant l' indexation basée sur n autorisent également les valeurs d'index négatives et d'autres types de données scalaires comme les énumérations , ou les caractères peuvent être utilisés comme index de tableau.

L'utilisation de l'indexation de base zéro est le choix de conception de nombreux langages de programmation influents, notamment C , Java et Lisp . Cela conduit à une implémentation plus simple où l'indice fait référence à un décalage par rapport à la position de départ d'un tableau, de sorte que le premier élément a un décalage de zéro.

Les tableaux peuvent avoir plusieurs dimensions, il n'est donc pas rare d'accéder à un tableau en utilisant plusieurs indices. Par exemple, un tableau Aà deux dimensions avec trois lignes et quatre colonnes peut donner accès à l'élément de la 2e ligne et de la 4e colonne par l'expression A[1][3]dans le cas d'un système d'indexation de base zéro. Ainsi, deux indices sont utilisés pour un tableau à deux dimensions, trois pour un tableau à trois dimensions et n pour un tableau à n dimensions.

Le nombre d'indices nécessaires pour spécifier un élément est appelé dimension, dimensionnalité ou rang du tableau.

Dans les tableaux standard, chaque index est limité à une certaine plage d'entiers consécutifs (ou des valeurs consécutives d'un certain type énuméré ), et l'adresse d'un élément est calculée par une formule "linéaire" sur les indices.

Tableaux à une dimension

Un tableau à une dimension (ou tableau à une dimension) est un type de tableau linéaire. L'accès à ses éléments implique un seul indice qui peut représenter un index de ligne ou de colonne.

A titre d'exemple, considérons la déclaration C int anArrayName[10];qui déclare un tableau à une dimension de dix entiers. Ici, le tableau peut stocker dix éléments de type int. Ce tableau a des indices allant de zéro à neuf. Par exemple, les expressions anArrayName[0]et anArrayName[9]sont respectivement le premier et le dernier élément.

Pour un vecteur à adressage linéaire, l'élément d'indice i est situé à l'adresse B + c × i , où B est une adresse de base fixe et c une constante fixe, parfois appelée incrément d'adresse ou foulée .

Si les indices d'élément valides commencent à 0, la constante B est simplement l'adresse du premier élément du tableau. Pour cette raison, le langage de programmation C spécifie que les indices de tableau commencent toujours à 0 ; et de nombreux programmeurs appelleront cet élément " zeroth " plutôt que " first ".

Cependant, on peut choisir l'indice du premier élément par un choix approprié de l'adresse de base B . Par exemple, si le tableau comporte cinq éléments, indexés de 1 à 5, et que l'adresse de base B est remplacée par B + 30 c , alors les indices de ces mêmes éléments seront de 31 à 35. Si la numérotation ne commence pas à 0, la constante B ne peut être l'adresse d'aucun élément.

Tableaux multidimensionnels

Pour un tableau multidimensionnel, l'élément avec les indices i , j aurait l'adresse B + c · i + d · j , où les coefficients c et d sont les incréments d'adresse de ligne et de colonne , respectivement.

Plus généralement, dans un tableau à k dimensions, l'adresse d'un élément d'indices i ₁ , i ₂ , ..., i _k est

B + c ₁ · i ₁ + c ₂ · i ₂ + … + c _k · i _k .

Par exemple : int a[2][3];

Cela signifie que le tableau a a 2 lignes et 3 colonnes, et le tableau est de type entier. Ici, nous pouvons stocker 6 éléments, ils seront stockés linéairement mais en commençant par la première ligne linéaire puis en continuant avec la deuxième ligne. Le tableau ci-dessus sera stocké comme un ₁₁ , un ₁₂ , un ₁₃ , un ₂₁ , un ₂₂ , un ₂₃ .

Cette formule ne nécessite que k multiplications et k additions, pour tout tableau pouvant tenir en mémoire. De plus, si un coefficient est une puissance fixe de 2, la multiplication peut être remplacée par un décalage de bits .

Les coefficients c _k doivent être choisis de telle sorte que chaque tuple d'index valide corresponde à l'adresse d'un élément distinct.

Si la valeur minimale légale pour chaque indice est 0, alors B est l'adresse de l'élément dont les indices sont tous nuls. Comme dans le cas unidimensionnel, les indices d'éléments peuvent être modifiés en changeant l'adresse de base B . Ainsi, si un tableau à deux dimensions a des lignes et des colonnes indexées de 1 à 10 et de 1 à 20, respectivement, le remplacement de B par B + c ₁ − 3 c ₂ entraînera leur renumérotation de 0 à 9 et de 4 à 23 , respectivement. Profitant de cette fonctionnalité, certains langages (comme FORTRAN 77) spécifient que les indices de tableau commencent à 1, comme dans la tradition mathématique tandis que d'autres langages (comme Fortran 90, Pascal et Algol) permettent à l'utilisateur de choisir la valeur minimale pour chaque indice.

Vecteurs de dopage

La formule d'adressage est entièrement définie par la dimension d , l'adresse de base B et les incréments c ₁ , c ₂ , ..., c _k . Il est souvent utile de regrouper ces paramètres dans un enregistrement appelé descripteur du tableau ou vecteur de foulée ou vecteur de dope . La taille de chaque élément et les valeurs minimales et maximales autorisées pour chaque indice peuvent également être incluses dans le vecteur de dope. Le vecteur dope est un handle complet pour le tableau et constitue un moyen pratique de transmettre des tableaux en tant qu'arguments aux procédures . De nombreuses opérations de découpage de tableau utiles (telles que la sélection d'un sous-tableau, l'échange d'indices ou l'inversion de la direction des indices) peuvent être effectuées très efficacement en manipulant le vecteur de dope.

Dispositions compactes

Souvent les coefficients sont choisis de telle sorte que les éléments occupent une zone de mémoire contiguë. Cependant, ce n'est pas nécessaire. Même si les tableaux sont toujours créés avec des éléments contigus, certaines opérations de découpage de tableau peuvent en créer des sous-tableaux non contigus.

Illustration de l'ordre principal des lignes et des colonnes

Il existe deux dispositions compactes systématiques pour un tableau à deux dimensions. Par exemple, considérons la matrice

${\displaystyle A={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}$

Dans la disposition de l'ordre des lignes principales (adoptée par C pour les tableaux déclarés statiquement), les éléments de chaque ligne sont stockés dans des positions consécutives et tous les éléments d'une ligne ont une adresse inférieure à celle de n'importe lequel des éléments d'une ligne consécutive :

1

2

3

4

5

6

7

8

9

Dans l'ordre des colonnes principales (traditionnellement utilisé par Fortran), les éléments de chaque colonne sont consécutifs en mémoire et tous les éléments d'une colonne ont une adresse inférieure à celle de n'importe lequel des éléments d'une colonne consécutive :

1

4

7

2

5

8

3

6

9

Pour les tableaux avec trois indices ou plus, "row major order" place dans des positions consécutives deux éléments dont les tuples d'index ne diffèrent que d'un dans le dernier index. « L'ordre majeur des colonnes » est analogue au premier indice.

Dans les systèmes qui utilisent le cache du processeur ou la mémoire virtuelle , le balayage d'un tableau est beaucoup plus rapide si les éléments successifs sont stockés dans des positions consécutives en mémoire, plutôt que dispersés de manière clairsemée. De nombreux algorithmes qui utilisent des tableaux multidimensionnels les analysent dans un ordre prévisible. Un programmeur (ou un compilateur sophistiqué) peut utiliser ces informations pour choisir entre une disposition principale en ligne ou en colonne pour chaque tableau. Par exemple, lors du calcul du produit A · B de deux matrices, il serait préférable de stocker A dans l'ordre des lignes principales et B dans l'ordre des colonnes.

Redimensionnement

Les tableaux statiques ont une taille fixe lors de leur création et ne permettent donc pas l'insertion ou la suppression d'éléments. Cependant, en allouant un nouveau tableau et en y copiant le contenu de l'ancien tableau, il est possible d'implémenter efficacement une version dynamique d'un tableau ; voir tableau dynamique . Si cette opération est peu fréquente, les insertions en fin de tableau ne nécessitent qu'un temps constant amorti.

Certaines structures de données de tableau ne réaffectent pas le stockage, mais stockent un nombre d'éléments du tableau en cours d'utilisation, appelé nombre ou taille. Cela fait de la baie une baie dynamique avec une taille ou une capacité maximale fixe ; Les chaînes Pascal en sont des exemples.

Formules non linéaires

Des formules plus compliquées (non linéaires) sont parfois utilisées. Pour un tableau triangulaire compact à deux dimensions , par exemple, la formule d'adressage est un polynôme de degré 2.

Efficacité

Les deux stockent et sélectionnent le temps constant de prise (le pire cas déterministe) . Les tableaux prennent un espace linéaire ( O ( n )) dans le nombre d'éléments n qu'ils contiennent.

Dans un tableau avec une taille d'élément k et sur une machine avec une taille de ligne de cache de B octets, l'itération dans un tableau de n éléments nécessite le minimum d' échecs de cache plafond ( nk /B), car ses éléments occupent des emplacements mémoire contigus. C'est à peu près un facteur de B/ k supérieur au nombre d'échecs de cache nécessaires pour accéder à n éléments à des emplacements mémoire aléatoires. En conséquence, l'itération séquentielle sur un tableau est sensiblement plus rapide en pratique que l'itération sur de nombreuses autres structures de données, une propriété appelée localité de référence (cela ne signifie cependant pas que l'utilisation d'un hachage parfait ou d' un hachage trivial dans le même tableau (local) , ne sera pas encore plus rapide - et réalisable en temps constant ). Les bibliothèques fournissent des fonctionnalités optimisées de bas niveau pour copier des plages de mémoire (telles que memcpy ) qui peuvent être utilisées pour déplacer des blocs contigus d' éléments de tableau beaucoup plus rapidement que ce qui peut être réalisé par l'accès aux éléments individuels. L'accélération de ces routines optimisées varie en fonction de la taille des éléments du tableau, de l'architecture et de l'implémentation.

Du point de vue de la mémoire, les tableaux sont des structures de données compactes sans surcharge par élément . Il peut y avoir un surcoût par tableau (par exemple, pour stocker les limites d'index), mais cela dépend de la langue. Il peut également arriver que des éléments stockés dans un tableau nécessitent moins de mémoire que les mêmes éléments stockés dans des variables individuelles, car plusieurs éléments de tableau peuvent être stockés dans un seul mot ; ces tableaux sont souvent appelés emballés tableaux. Un cas extrême (mais couramment utilisé) est le tableau de bits , où chaque bit représente un élément unique. Un seul octet peut ainsi contenir jusqu'à 256 combinaisons différentes de jusqu'à 8 conditions différentes, sous la forme la plus compacte.

Les accès aux tableaux avec des modèles d'accès statiquement prévisibles sont une source majeure de parallélisme des données .

Comparaison avec d'autres structures de données

Les tableaux dynamiques ou les tableaux extensibles sont similaires aux tableaux mais ajoutent la possibilité d'insérer et de supprimer des éléments ; l'ajout et la suppression à la fin est particulièrement efficace. Cependant, ils se réservent linéaire ( Θ ( n stockage supplémentaire)), alors que les tableaux ne réservent pas de stockage supplémentaire.

Les tableaux associatifs fournissent un mécanisme pour une fonctionnalité de type tableau sans frais de stockage énormes lorsque les valeurs d'index sont rares. Par exemple, un tableau qui contient des valeurs uniquement aux index 1 et 2 milliards peut bénéficier de l'utilisation d'une telle structure. Les tableaux associatifs spécialisés avec des clés entières comprennent les tableaux de Patricia , les tableaux de Judy et les arbres de van Emde Boas .

Les arbres équilibrés nécessitent un temps O(log n ) pour l'accès indexé, mais permettent également d'insérer ou de supprimer des éléments dans un temps O(log n ), tandis que les tableaux extensibles nécessitent un temps linéaire (Θ( n )) pour insérer ou supprimer des éléments à une position arbitraire.

Les listes chaînées permettent une suppression et une insertion en temps constant au milieu, mais prennent un temps linéaire pour l'accès indexé. Leur utilisation de la mémoire est généralement pire que celle des tableaux, mais reste linéaire.

Un vecteur d'Iliffe est une alternative à une structure matricielle multidimensionnelle. Il utilise un tableau unidimensionnel de références à des tableaux d'une dimension de moins. Pour deux dimensions, en particulier, cette structure alternative serait un vecteur de pointeurs vers des vecteurs, un pour chaque ligne (pointeur sur c ou c++). Ainsi, un élément de la ligne i et de la colonne j d'un tableau A serait accessible par double indexation ( A [ i ][ j ] en notation typique). Cette structure alternative autorise les tableaux irréguliers , où chaque ligne peut avoir une taille différente ou, en général, où la plage valide de chaque index dépend des valeurs de tous les index précédents. Cela permet également d'économiser une multiplication (par l'incrément d'adresse de colonne) en la remplaçant par un décalage de bit (pour indexer le vecteur de pointeurs de ligne) et un accès mémoire supplémentaire (récupérer l'adresse de ligne), ce qui peut être intéressant dans certaines architectures.

Dimension

La dimension d'un tableau est le nombre d'indices nécessaires pour sélectionner un élément. Ainsi, si le tableau est vu comme une fonction sur un ensemble de combinaisons d'indices possibles, c'est la dimension de l'espace dont son domaine est un sous-ensemble discret. Ainsi, un tableau à une dimension est une liste de données, un tableau à deux dimensions est un rectangle de données, un tableau à trois dimensions un bloc de données, etc.

Cela ne doit pas être confondu avec la dimension de l'ensemble de toutes les matrices avec un domaine donné, c'est-à-dire le nombre d'éléments dans le tableau. Par exemple, un tableau avec 5 lignes et 4 colonnes est bidimensionnel, mais de telles matrices forment un espace à 20 dimensions. De même, un vecteur tridimensionnel peut être représenté par un tableau unidimensionnel de taille trois.

Voir également

Les références