Type de données de tableau - Array data type

En informatique , un type de tableau est un type de données qui représente une collection d' éléments ( valeurs ou variables ), chacun sélectionné par un ou plusieurs indices (clés d'identification) qui peuvent être calculés au moment de l'exécution lors de l'exécution du programme. Une telle collection est généralement appelée variable tableau , valeur de tableau , ou tout simplement tableau . Par analogie avec les concepts mathématiques vecteur et matrice , les types de tableau avec un et deux indices sont souvent appelés respectivement type vecteur et type matrice . Plus généralement, un type tableau multidimensionnel peut être appelé un type tenseur .

La prise en charge du langage pour les types de tableau peut inclure certains types de données de tableau intégrés , certaines constructions syntaxiques ( constructeurs de type de tableau ) que le programmeur peut utiliser pour définir de tels types et déclarer des variables de tableau, et une notation spéciale pour l'indexation des éléments de tableau. Par exemple, dans le langage de programmation Pascal , la déclaration type MyTable = array [1..4,1..2] of integer, définit un nouveau type de données tableau appelé MyTable. La déclaration var A: MyTabledéfinit alors une variable Ade ce type, qui est un agrégat de huit éléments, chacun étant une variable entière identifiée par deux indices. Dans le programme Pascal, ces éléments sont notés A[1,1], A[1,2], A[2,1], …, A[4,2]. Les types de tableaux spéciaux sont souvent définis par les bibliothèques standard du langage .

Les listes dynamiques sont également plus courantes et plus faciles à mettre en œuvre que les tableaux dynamiques . Les types tableau se distinguent des types enregistrement principalement parce qu'ils permettent de calculer les indices d'élément au moment de l'exécution , comme dans l' affectation Pascal A[I,J] := A[N-I,2*J]. Entre autres choses, cette fonctionnalité permet à une seule instruction itérative de traiter arbitrairement de nombreux éléments d'une variable de tableau.

Dans des contextes plus théoriques, notamment en théorie des types et dans la description d' algorithmes abstraits , les termes « tableau » et « type de tableau » font parfois référence à un type de données abstrait (ADT) également appelé tableau abstrait ou peuvent désigner un tableau associatif , un modèle mathématique avec les opérations de base et le comportement d'un type de tableau typique dans la plupart des langages - essentiellement, une collection d'éléments sélectionnés par des indices calculés au moment de l'exécution.

Selon la langue, les types de tableau peuvent chevaucher (ou être identifiés avec) d'autres types de données qui décrivent des agrégats de valeurs, tels que des listes et des chaînes . Les types de tableau sont souvent implémentés par des structures de données de tableau , mais parfois par d'autres moyens, tels que des tables de hachage , des listes chaînées ou des arbres de recherche .

Histoire

Le langage de programmation Superplan de Heinz Rutishauser (1949-1951) comprenait des tableaux multidimensionnels. Rutishauser cependant, bien que décrivant comment un compilateur pour son langage devrait être construit, n'en a pas implémenté un.

Les langages d'assemblage et les langages de bas niveau comme BCPL n'ont généralement pas de support syntaxique pour les tableaux.

En raison de l'importance des structures de tableaux pour un calcul efficace, les premiers langages de programmation de haut niveau, notamment FORTRAN (1957), COBOL (1960) et Algol 60 (1960), ont pris en charge les tableaux multidimensionnels.

Tableaux abstraits

Une structure de données de tableau peut être modélisée mathématiquement comme une structure de données abstraite (un tableau abstrait ) avec deux opérations

get ( A , I ) : les données stockées dans l'élément du tableau A dont les indices sont le tuple entier I .

set ( A , I , V ): le tableau qui résulte en définissant la valeur de cet élément sur V .

Ces opérations sont nécessaires pour satisfaire les axiomes

obtenir ( définir ( A , I , V ), I ) = V

obtenir ( set ( A , I , V ), J ) = get ( A , J ) si I ≠ J

pour tout état de tableau A , toute valeur V et tout tuple I , J pour lesquels les opérations sont définies.

Le premier axiome signifie que chaque élément se comporte comme une variable. Le deuxième axiome signifie que les éléments avec des indices distincts se comportent comme des variables disjointes , de sorte que le stockage d'une valeur dans un élément n'affecte la valeur d'aucun autre élément.

Ces axiomes n'imposent aucune contrainte sur l'ensemble des tuples d'indice valides I , ce modèle abstrait peut donc être utilisé pour des matrices triangulaires et d'autres tableaux de forme étrange.

Implémentations

Afin d'implémenter efficacement des variables de types tels que les structures de tableau (avec l'indexation effectuée par l' arithmétique du pointeur ), de nombreux langages restreignent les indices aux types de données entiers (ou à d'autres types pouvant être interprétés comme des entiers, tels que les octets et les types énumérés ), et exigent que tous les éléments aient le même type de données et la même taille de stockage. La plupart de ces langages restreignent également chaque index à un intervalle fini d'entiers, qui reste fixe pendant toute la durée de vie de la variable de tableau. Dans certains langages compilés , en fait, les plages d'index peuvent devoir être connues au moment de la compilation .

D'autre part, certains langages de programmation fournissent des types de tableaux plus libéraux, qui permettent l'indexation par des valeurs arbitraires, telles que des nombres à virgule flottante , des chaînes , des objets , des références , etc. De telles valeurs d'index ne peuvent pas être limitées à un intervalle, encore moins à un intervalle fixe. Ainsi, ces langages permettent généralement de créer de nouveaux éléments arbitraires à tout moment. Ce choix exclut la mise en œuvre de types de tableaux en tant que structures de données de tableaux. C'est-à-dire que ces langages utilisent une syntaxe de type tableau pour implémenter une sémantique de tableau associatif plus générale , et doivent donc être implémentés par une table de hachage ou une autre structure de données de recherche .

Support linguistique

Tableaux multidimensionnels

Le nombre d'indices nécessaires pour spécifier un élément est appelé dimension , dimensionnalité ou rang du type de tableau. (Cette nomenclature est en conflit avec le concept de dimension en algèbre linéaire, où c'est le nombre d'éléments. Ainsi, un tableau de nombres avec 5 lignes et 4 colonnes, donc 20 éléments, est dit avoir la dimension 2 dans les contextes informatiques, mais représente une matrice de dimension 4 sur 5 ou 20 en mathématiques. De plus, la signification informatique de « rang » est similaire à sa signification en algèbre tensorielle mais pas au concept d'algèbre linéaire de rang d'une matrice .)

De nombreux langages ne prennent en charge que les tableaux à une dimension. Dans ces langues, un tableau multidimensionnel est généralement représenté par un vecteur Iliffe , un tableau unidimensionnel de références à des tableaux d'une dimension de moins. Un tableau à deux dimensions, en particulier, serait implémenté comme un vecteur de pointeurs vers ses lignes. 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 façon d'émuler des tableaux multidimensionnels permet la création de 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.

Cette représentation des tableaux multidimensionnels est assez répandue dans les logiciels C et C++. Cependant, C et C++ utiliseront une formule d'indexation linéaire pour les tableaux multidimensionnels déclarés avec une taille constante au moment de la compilation, par exemple par int A[10][20]ou int A[m][n], au lieu du traditionnel int **A.

Notation d'indexation

La plupart des langages de programmation qui prennent en charge les tableaux prennent en charge les opérations de stockage et de sélection et ont une syntaxe spéciale pour l'indexation. Les premières langues utilisaient des parenthèses, par exemple A(i,j), comme en FORTRAN ; d'autres choisissent des crochets, par exemple A[i,j]ou A[i][j], comme dans Algol 60 et Pascal (à distinguer de l'utilisation de parenthèses pour les appels de fonction ).

Types d'index

Les types de données de tableau sont le plus souvent implémentés sous forme de structures de tableau : avec des indices limités à des valeurs entières (ou totalement ordonnées), des plages d'indices fixées au moment de la création du tableau et un adressage d'éléments multilinéaire. C'était le cas dans la plupart des langages de "troisième génération" , et c'est toujours le cas de la plupart des langages de programmation système tels que Ada , C et C++ . Dans certains langages, cependant, les types de données de tableau ont la sémantique des tableaux associatifs, avec des indices de type arbitraire et la création d'éléments dynamiques. C'est le cas de certains langages de script tels que Awk et Lua , et de certains types de tableaux fournis par les bibliothèques C++ standard .

Vérification des limites

Certains langages (comme Pascal et Modula) effectuent une vérification des limites à chaque accès, levant une exception ou l'abandon du programme lorsqu'un index est hors de sa plage valide. Les compilateurs peuvent autoriser la désactivation de ces contrôles pour échanger la sécurité contre la vitesse. D'autres langages (comme FORTRAN et C) font confiance au programmeur et n'effectuent aucune vérification. Les bons compilateurs peuvent également analyser le programme pour déterminer la plage de valeurs possibles que l'index peut avoir, et cette analyse peut conduire à l' élimination de la vérification des limites .

Origine de l'index

Certains langages, tels que C, ne fournissent que des types de tableaux de base zéro , pour lesquels la valeur minimale valide pour tout indice est 0. Ce choix est pratique pour l'implémentation de tableaux et les calculs d'adresses. Avec un langage tel que C, un pointeur vers l'intérieur de n'importe quel tableau peut être défini qui agira symboliquement comme un pseudo-tableau qui s'adapte aux indices négatifs. Cela fonctionne uniquement parce que C ne vérifie pas un index par rapport aux limites lorsqu'il est utilisé.

D'autres langages ne fournissent que des types de tableaux basés sur un , où chaque index commence à 1 ; c'est la convention traditionnelle en mathématiques pour les matrices et les suites mathématiques . Quelques langages, tels que Pascal et Lua, prennent en charge les types de tableaux basés sur n , dont les indices légaux minimaux sont choisis par le programmeur. Les mérites relatifs de chaque choix ont fait l'objet de vifs débats. L'indexation à base zéro permet d'éviter les erreurs un par un ou les erreurs de poteau de clôture , en particulier un for(i=0;i<5;i+=1) basé sur 0 itère (5-0) fois, tandis que dans la moitié équivalente basée sur 1 -open range for(i=1;i<6;i+=1) le 6 est lui-même une erreur potentielle de ce type, nécessitant généralement length()+1, et la plage inclusive basée sur 1 pour(i=1;i<= 5;i+=1) itère (5-1)+1 fois.

Voir la comparaison des langages de programmation (tableau) pour les indices de base utilisés par divers langages.

Indice le plus élevé

La relation entre les nombres apparaissant dans une déclaration de tableau et l'index du dernier élément de ce tableau varie également selon la langue. Dans de nombreux langages (tels que C), il faut spécifier le nombre d'éléments contenus dans le tableau ; alors que dans d'autres (tels que Pascal et Visual Basic .NET ) il faut spécifier la valeur numérique de l'index du dernier élément. Inutile de dire que cette distinction est sans importance dans les langues où les indices commencent à 1, comme Lua .

Algèbre matricielle

Certains langages de programmation prennent en charge la programmation de tableaux , où les opérations et fonctions définies pour certains types de données sont implicitement étendues aux tableaux d'éléments de ces types. Ainsi on peut écrire A + B pour additionner les éléments correspondants de deux tableaux A et B . Habituellement, ces langages fournissent à la fois la multiplication élément par élément et le produit matriciel standard de l'algèbre linéaire , et lequel d'entre eux est représenté par l' opérateur * varie selon le langage.

Les langages offrant des capacités de programmation de tableaux ont proliféré depuis les innovations dans ce domaine de l' APL . Il s'agit de capacités essentielles de langages spécifiques à un domaine tels que GAUSS , IDL , Matlab et Mathematica . Il s'agit d'une installation centrale dans les langages les plus récents, tels que Julia et les versions récentes de Fortran . Ces capacités sont également fournies via des bibliothèques d'extensions standard pour d'autres langages de programmation à usage général (comme la bibliothèque NumPy largement utilisée pour Python ).

Types de chaînes et tableaux

De nombreux langages fournissent un type de données de chaîne intégré , avec une notation spécialisée (" string literals ") pour créer des valeurs de ce type. Dans certains langages (comme le C), une chaîne n'est qu'un tableau de caractères ou est gérée de la même manière. D'autres langages, comme Pascal , peuvent fournir des opérations très différentes pour les chaînes et les tableaux.

Requêtes de plage d'index de tableau

Certains langages de programmation fournissent des opérations qui renvoient la taille (nombre d'éléments) d'un vecteur, ou, plus généralement, la plage de chaque index d'un tableau. En C et C++, les tableaux ne prennent pas en charge la fonction de taille , les programmeurs doivent donc souvent déclarer une variable distincte pour contenir la taille et la transmettre aux procédures en tant que paramètre distinct.

Les éléments d'un tableau nouvellement créé peuvent avoir des valeurs indéfinies (comme en C), ou peuvent être définis pour avoir une valeur "par défaut" spécifique telle que 0 ou un pointeur nul (comme en Java).

En C++, un objet std::vector prend en charge les opérations store , select et append avec les caractéristiques de performances décrites ci-dessus. Les vecteurs peuvent être interrogés pour leur taille et peuvent être redimensionnés. Les opérations plus lentes comme l'insertion d'un élément au milieu sont également prises en charge.

Trancher

Une opération de découpage de tableau prend un sous-ensemble des éléments d'une entité de type tableau (valeur ou variable), puis les assemble comme une autre entité de type tableau, éventuellement avec d'autres indices. Si les types de tableau sont implémentés en tant que structures de tableau, de nombreuses opérations de découpage 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 de la structure. Les découpages possibles dépendent des détails d'implémentation : par exemple, FORTRAN permet de découper une colonne d'une variable matricielle, mais pas une ligne, et de la traiter comme un vecteur ; alors que C permet de découper une ligne d'une matrice, mais pas une colonne.

D'un autre côté, d'autres opérations de découpage sont possibles lorsque les types de tableau sont implémentés d'autres manières.

Redimensionnement

Certaines langues permettent des tableaux dynamiques (aussi appelés redimensionnable , Growable ou extensible ): variables de tableau dont les gammes index peut être étendu à tout moment après la création, sans changer les valeurs de ses éléments actuels.

Pour les tableaux à une dimension, cette fonction peut être fournie sous la forme d'une opération " append( A , x )" qui augmente la taille du tableau A d'une unité, puis définit la valeur du dernier élément sur x . D'autres types de tableaux (tels que les chaînes Pascal) fournissent un opérateur de concaténation, qui peut être utilisé avec le découpage pour obtenir cet effet et plus encore. Dans certains langages, l'affectation d'une valeur à un élément d'un tableau étend automatiquement le tableau, si nécessaire, pour inclure cet élément. Dans d'autres types de tableau, une tranche peut être remplacée par un tableau de taille différente" avec les éléments suivants renumérotés en conséquence - comme dans l'affectation de liste de Python " A [5:5] = [10,20,30]", qui insère trois nouveaux éléments (10, 20 et 30) avant l'élément " A [5] ". Les tableaux redimensionnables sont conceptuellement similaires aux listes , et les deux concepts sont synonymes dans certains langages.

Un tableau extensible peut être implémenté sous la forme d'un tableau de taille fixe, avec un compteur qui enregistre le nombre d'éléments réellement utilisés. L' appendopération incrémente simplement le compteur ; jusqu'à ce que tout le tableau soit utilisé, lorsque l' appendopération peut être définie comme un échec. Il s'agit d'une implémentation d'un tableau dynamique avec une capacité fixe, comme dans le stringtype de Pascal. Alternativement, l' appendopération peut réaffecter le tableau sous-jacent avec une taille plus grande et copier les anciens éléments dans la nouvelle zone.

Languages

In other projects