1 2 1 1 Fiche Tableaux
Les Tableaux¶
Introduction¶
Le tableau est une structure linéaire à accès direct, mutable, qui permet de manipuler un nombre fini \(n\) de valeurs indexées par les entiers de 0 à \(n - 1\). Il existe deux types de tableaux :
- le tableau statique dont les éléments sont tous du même type et dont la taille est fixée une fois pour toute à la création du tableau. C'est le cas des tableaux des langages C, Java, OCaml.
- le tableau dynamique dont la taille n'est pas fixe et dont les éléments peuvent avoir des types différents (Python, JavaScript).
Les tableaux de Python sont des tableaux dynamiques et implémentés par un objet de type list
.
Attention, en mathématiques le terme tableau désigne une structure à 2 dimensions (des lignes et des colonnes) qu'on appelle aussi matrice. Évidemment on pourra utiliser des tableaux informatiques pour modéliser des matrices.
Syntaxiquement, voici une list
Python :
['python', -1, 3.14, True, (1, 2, 3), [0, 0]]
Les éléments sont entourés de crochets et séparés par une virgule. Donnez le type de chacun des éléments de ce tableau. Dans le cadre du programme officiel, les tableaux que nous manipulerons seront constitués d'éléments de même type.
Et la list
vide :
[]
Exemple d'utilisation de tableau¶
Une image matricielle est constituée de pixels rangés en lignes et colonnes formant ainsi une matrice, au sens mathématique du terme. S'il s'agit d'une image noir et blanc, chaque pixel peut être vu comme un entier entre 0 et 255, représentant une nuance de gris. Une image de 200 pixels de large et 100 pixels de haut pourra donc être modélisée et manipulée sous la forme d'un tableau de 20000 valeurs entières ou un tableau de 100 tableaux chacun de 200 valeurs entières.
Voir l'exemple de l'image : lumni.fr
Construire un tableau¶
En extension¶
On peut créer un tableau en extension c'est-à-dire en listant chacun de ses éléments, comme déjà vu :
>>> temperatures_min = [-5.2, -6.4, -1.3, 1.2, 7.5, 12.8, 18.4, 17.6, 12.1, 9.6, 9.8, 4.6]
Cette façon de procéder ne va que pour de petits tableaux et devient inutilisable lorsque le nombre d'éléments est trop important.
Par concaténation multiple¶
La list
étant une séquence, on peut la concaténer :
>>> debut = [1, 2, 3]
>>> fin = [4, 5]
>>> tableau_entier = debut + fin
>>> tableau_entier
[1, 2, 3, 4, 5]
Et utiliser la concaténation multiple pour créer rapidement une list
avec une valeurs initiale pour chacune des composantes :
>>> zeros = [0] * 10
Mise en garde
Une règle à respecter lors de la création d'un tableau par concaténation multiple : les éléments du tableau doivent être des objets immuables. Dans la partie compléments, nous verrons pourquoi.
Par compréhension¶
Cette construction est proche de la notion mathématique des ensembles définis en compréhension. Elle s'appuie sur un référentiel (le domaine dans lequel sont pris les éléments), une fonction de transformation des éléments (éventuellement la fonction identité) et une propriété définissante ou contrainte.
Voici par exemple la définition en compréhension de l'ensemble des entiers naturels pairs :
Les tableaux infinis n'existent pas. Voici en compréhension le tableau des 10 premiers nombres pairs :
>>> [2 * i for i in range(1, 11)]
Le référentiel est range(1, 11)
, la fonction de transformation : \(f(x) : 2 * x\) et la contrainte vide.
On peut utiliser cette compréhension pour l'initialisation de notre tableau zeros
:
>>> zeros = [0 for _ in range(10)]
L'utilisation de _
comme variable dans le for
permet d'insister sur le fait que la boucle ne sert que de compteur et que la valeur de ce compteur nous importe peu.
Un dernier exemple, le tableau des 10 premiers carrés :
>>> carres = [i ** 2 for i in range(1, 11)]
Notons ici que la boucle est plus qu'un simple compteur et les valeurs de la variable de boucle sont utilisées pour construire notre tableau.
Par ajout à partir de la list
vide¶
Il s'agit alors d'un tableau dynamique. La méthode utilisée est append
qui modifie la list
appelante en lui ajoutant un élément à la fin :
>>> ma_liste = [10, 100]
>>> ma_liste.append(1000)
>>> ma_liste
[10, 100, 1000]
Pour notre tableau des 10 premiers carrés :
>>> carres = []
>>> for a in range(1, 11):
carres.append(a ** 2)
Par la fonction list
¶
Nous avons déjà rencontré la fonction int()
qui permet, notamment, de contruire un entier à partir d'une chaîne de caractères :
>>> int('1000') + 1
1001
La fonction list()
permet d'obtenir une list
à partir d'un itérable :
>>> list(range(6))
[0, 1, 2, 3, 4, 5]
>>> list('Hello !')
['H', 'e', 'l', 'l', 'o', ' ', '!']
Manipuler un tableau¶
Accès¶
En tant que séquence la list
offre un accès direct aux éléments grâce aux crochets auxquels on passe un indice entier :
>>> fruits = ['pomme', 'mangue', 'orange']
>>> fruits[0]
'pomme'
N'oubliez pas que, comme pour toutes les séquences de Python le premier indice est 0. On peut accéder aux composantes par la fin, avec des indices négatifs :
>>> fruits[-2]
'mangue'
Attention tenter d'accéder à un élément du tableau avec un indice trop grand ou trop petit provoque une IndexError
:
>>> fruits = ['pomme', 'mangue', 'orange']
>>> fruits[3]
----> 1 fruits[3]
IndexError: list index out of range
Modification¶
Nous en avons déjà parlé, la list
est un objet muable ou mutable en anglais. Cela signifie que l'on peut changer la valeur d'une composante du tableau. Mais pour bien comprendre la partie en italique de cette phrase, il nous faut approfondir encore. En effet, si on considère le tableau des fruits ci-dessus, dire qu'on peut changer par exemple la première composante pourrait laisser croire qu'on peut modifier la chaîne de caractères 'pomme'
. Or les chaînes de caractères sont immuables.
Il faut retenir que le tableau est un tableau de références vers les objets. Le diagramme ci-dessous obtenu via l'outil pythontutor permet de visualiser cela :
Dès lors, changer la première composante revient à changer la flèche pour la faire pointer vers un autre objet.
>>> fruits[0] = 'pêche'
>>> fruits
['pêche', 'mangue', 'orange']
Voici le nouveau diagramme associé :
Mais qu'est-il arrivé à l'objet 'pomme'
? N'étant plus référencé il a été nettoyé par le ramasse-miette (garbage collector en anglais) de Python dont le rôle est de libérer l'espace mémoire non utilisé. Si on crée une autre référence (un alias) vers 'pomme'
on réalise mieux le changement de référence produit par fruits[0] = 'pêche'
:
On le constate : on n'a pas touché à 'pomme'
mais créé un nouvel objet str
: 'pêche'
et fruits[0]
référence maintenant ce nouvel objet.
Parcourir un tableau¶
La boucle for
est le moyen le plus commode pour parcourir les éléments d'un tableau, comme pour n'importe quelle séquence de Python.
Parcourir les indices¶
En utilisant la fonction range
on peut obtenir et parcourir les entiers de 0 à \(n - 1\) et ensuite accéder à l'élément du tableau figurant à l'indice courant :
>>> for i in range(3):
traiter(fruits[i])
On fera attention à une des erreurs les plus courantes en programmation : l'IndexError
obtenue par accès avec un indice trop grand. Dans l'exemple ci-dessus, notre tableau de fruits comporte trois éléments d'indices 0, 1 et 2. Si on remplace le 3 de la fonction range
par un 4 on aura une erreur : la tentative d'accès à fruits[3]
.
La fonction len
donne la taille du tableau et peut être utilisée conjointement à range
:
>>> for i in range(len(fruits)):
traiter(fruits[i])
Un schéma classique sur les tableaux est l'initialisation d'un tableau avec des valeurs fantômes (0 par exemple) puis la modification de chaque élément du tableau.
>>> carres = [0] * 10
>>> for i in range(len(carres)):
carres[i] = (i + 1) ** 2
>>> carres
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
Parcourir directement les éléments¶
Il s'agit là d'une particuliarité de la boucle for
de Python qui se rapproche de la boucle for..of de JavaScript.
for fruit in fruits:
traiter(fruit)
On constate que la lisibilité est bien meilleure qu'avec les indices. Il semble judicieux de privilégier le parcours par les éléments tant que les indices ne sont pas nécessaires. Les indices sont nécessaires dans les cas suivants :
-
parcours simultané de plusieurs séquences : voici une fonction qui retourne
True
si et seulement si les deux séquences (supposées de même longueur) passées en paramètres coïncident c'est-à-dire que leurs éléments sont égaux.def egaux(s1, s2): for i in range(len(s1)): if s1[i] != s2[i]: return False return True
2. modification du tableau (voir l'exemple descarres
)
Compléments¶
Test d'appartenance¶
L'opérateur in
permet de savoir si un élément appartient à une list
:
>>> grande_liste = list(range(1000000))
>>> 145 in grande_liste
True
>>> -1 in grande_liste
False
Si vous avez testé l'exemple ci-dessus vous vous êtes rendu compte que la réponse à la deuxième interrogation n'est pas immédiate. En effet le test d'appartenance sur une séquence est en temps linéaire en fonction du nombre d'éléments. C'est à prendre en considération lors du choix de la stucture pour modéliser un problème : si les tests d'appartenance sont nombreux peut-être qu'il faudra faire un autre choix que celui du tableau.
Pourquoi liste et pas tableau ?¶
Difficile de trouver une explication sur le choix de list
par les concepteurs. JavaScript qui utilise aussi des tableaux dynamiques du même genre à utilisé le terme Array
qui signifie bien tableau.
Le principal avantage du tableau est l'accès rapide à ses éléments (on parle de temps constant ou O(1), voir le chapitre Algorithmique). Cette efficacité est possible sur le tableau statique car il est constitué de cellules mémoires contigues. Connaissant le type d'un élément (donc sa taille en mémoire) et l'indice de l'élément recherché, un simple calcul d'adresse permet de trouver la case mémoire de cet élément. Mais dans cette configuration, le retrait et l'ajout d'éléments dans le tableau sont impossibles.
Python a opté pour une autre solution. Lors de la création d'une list
d'objets, un tableau de cellules contiguës de références vers ces objets est créé, plus grand que le nombre d'éléments dans la list
. Ainsi on a, comme tout tableau, un accès rapide à n'importe quel élément, et ce quelque soit sa taille tout en gardant la possibilité d'ajouter des éléments. Cet ajout, s'il est fait en fin de list
(par la méthode append
), se fait le plus souvent en temps constant. Sauf quand le tableau des références est plein : il faut alors en créer un nouveau plus grand et effectuer une recopie (voir par exemple la FAQ officielle sur le sujet).
Le retrait en fin de list
est aussi une opération efficace.
Néanmoins, les list
de Python sont bien des tableaux dynamiques et non des listes chaînées comme celles de LISP.
Les list
de list
¶
Nous en parlions en introduction de ce chapitre, les tableaux de tableaux sont possibles et même très utilisés :
>>> matrice = [[1, 2, 3], [4, 5, 6]]
>>> matrice[0]
[1, 2, 3]
>>> matrice[-1]
[4, 5, 6]
>>> matrice[0][2]
3
Analysez bien les appels ci-dessus : il n'y a aucune nouveauté. L'opérateur crochet associé à des indices entiers permet d'accèder aux éléments de mes list
... et quand l'élément est lui-même une list
on peut à nouveau lui appliquer l'opérateur crochet.
Le piège de la concaténation multiple¶
Nous l'évoquions : la construction par concaténation multiple ne doit se faire que pour des tableaux dont les éléments sont des objets immuables. Pourquoi ? Regardons un exemple :
>>> ligne = [0, 0, 0]
>>> matrice = [ligne] * 3
Voici le diagramme d'état issu de ces deux affectations :
On constate que notre "matrice" est en réalité une structure bizarre constituée de trois références vers la même et unique list
[0, 0, 0]
. Ce qui explique ceci :
>>> matrice[0][0] = 1 # on change la première valeur de la première ligne
>>> matrice
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]
Une bonne façon de faire ici serait :
ligne = [0] * 3 # ici la concaténation multiple est autorisée
matrice = [[e for e in ligne] for _ in range(3)]
On peut utiliser la méthode copy()
qui réalise une shallow copy ie une copie superficielle ou de premier niveau (par opposition à deepcopy non disponible dans la librairie standard mais dans le module copy
).
ligne = [0] * 3
matrice = [ligne.copy() for _ in range(3)]
Attention La manipulation de structures complexes mélangeant notamment des structures mutables peut s'avérer délicate. Il n'existe pas de fonction prédéfinie de Python qui teste l'égalité de deux structures. La simple égalité ==
n'étant bien sûr pas suffisante puisque :
>>> [[0]*3]*3 == [[0]*3 for _ in range(3)]
True
Alors même que, nous venons de le voir, ces deux structures sont différentes.
Quelques méthodes et fonctions sur les list
¶
Ci-dessous, nous présentons quelques unes des nombreuses méthodes et fonctions qui manipulent les listes. La plupart font que l'ont n'est plus dans du tableau statique mais bien avec un tableau dynamique. Ne pas hésiter à compléter par des recherches personnelles.
len(seq)
: fonction qui n'est pas spécifique auxlist
et qui retourne le nombre d'éléments contenu dans la séquenceseq
:>>> len([]) 0 >>> len([10, 10]) 2
append(elt)
: ajoute un élément en fin delist
, modifie lalist
>>> ma_liste = [1, 2, 3] >>> ma_liste.append(4) >>> ma_liste [1, 2, 3, 4]
pop()
: retourne le dernier élément de lalist
et le supprime de lalist
:>>> ma_liste.pop() 4 >>> ma_liste [1, 2, 3]
pop(ind)
: retourne l'élément d'indiceind
et le supprime de lalist
(attention cette opération reconstruit la liste entièrement et est donc coûteuse) :>>> ma_liste.pop(1) 2 >>> ma_liste [1, 3]
insert(ind, elt)
: insère à l'indiceind
l'élémentelt
(attention cette opération est plus coûteuse en général queappend
) :À noter que donner un indice trop grand ne provoque pas d'erreur mais ajoute à la fin :>>> ma_liste.insert(2, 10) >>> ma_liste [1, 3, 10]
>>> ma_liste.insert(5, 10) >>> ma_liste [1, 3, 10, 10]
-
sort(key, reverse)
: trie en place (ie modifie lalist
) suivant la fonctionkey
(la valeur par défaut est l'identité) et dans l'ordre croissant si le booléenreverse
est àFalse
(valeur par défaut) :>>> entiers = [5, 3, 1, 4, 2] >>> entiers.sort() >>> entiers [1, 2, 3, 4, 5]
->>> langages = ['python', 'java', 'c', 'swift'] >>> langages.sort(key=lambda e: len(e), reverse=True) >>> langages ['python', 'swift', 'java', 'c']
sorted(iterable, key, reverse)
: fonction qui prend un itérable et retourne une liste triée. Les autres paramètres fonctionnent comme pour la méthodesort()
:>>> sorted('bonjour') ['b', 'j', 'n', 'o', 'o', 'r', 'u']