Skip to content

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 :

  1. 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.
  2. 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 :

\[\left\{ x\in \mathbb{N}\ \Big\vert\ x\div 2\in \mathbb{N}\right\}\]

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 :

diagramme tableau

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é :

diagramme tableau2

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' :

diagramme tableau3

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 :

  1. 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 des carres)

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 :

Diag tableau de tableaux

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 aux list et qui retourne le nombre d'éléments contenu dans la séquence seq :
    >>> len([])
    0
    >>> len([10, 10])
    2
    
  • append(elt) : ajoute un élément en fin de list, modifie la list
    >>> ma_liste = [1, 2, 3]
    >>> ma_liste.append(4)
    >>> ma_liste
    [1, 2, 3, 4]
    
  • pop() : retourne le dernier élément de la list et le supprime de la list :
    >>> ma_liste.pop()
    4
    >>> ma_liste
    [1, 2, 3]
    
  • pop(ind) : retourne l'élément d'indice ind et le supprime de la list (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'indice ind l'élément elt (attention cette opération est plus coûteuse en général que append) :
    >>> ma_liste.insert(2, 10)
    >>> ma_liste
    [1, 3, 10]
    
    À noter que donner un indice trop grand ne provoque pas d'erreur mais ajoute à la fin :
    >>> ma_liste.insert(5, 10)
    >>> ma_liste
    [1, 3, 10, 10]
    
  • sort(key, reverse) : trie en place (ie modifie la list) suivant la fonction key (la valeur par défaut est l'identité) et dans l'ordre croissant si le booléen reverse 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éthode sort() :
    >>> sorted('bonjour')
    ['b', 'j', 'n', 'o', 'o', 'r', 'u']