Séquences : type tuple et list¶

Les types de données dits « simples » sont :

int (nombres entiers) ;
float (nombres flottants) ;
bool (booléens) ;
str (chaîne de caractères).

Ces types simples ne sont plus suffisants si nous avons besoin de garder en mémoire un grand nombre de valeurs. L’objectif est donc de construire un type de données capable de contenir plusieurs valeurs.

Nous allons étudier dans ce cours les séquences :

Les p-uplets (tuples)
Les listes

Les séquences permettent de stocker des éléments de manière ordonnée. Cet ordre sera représenté par un indice, c'est à a dire par un entier : 0, 1, 2, 3, ... , \(n-1\).

Dans un autre cours nous verrons les dictionnaires.

Les p-uplets (tuples)¶

Supposons que je souhaite stocker des coordonnées de points qui ne changeront pas par la suite pour les afficher ensuite sur un graphique. Je peux choisir de représenter les coordonnées en abscisse et en ordonnée par un tuple :

coordonnees = (1.0, 4.5)

On aurait aussi pu créer deux variables :

x = 1.0
y = 4.5

L'avantage d'utiliser des tuples dans ce cas est d'une part la clarté : la syntaxe est très proche de la représentation en mathématiques des coordonnées.

D'autre part le type tuple est "immuable" ("immutable" en anglais), c'est à dire qu'on ne peut pas le modifier après sa création.

début

Dans les séquences (tuples et listes en ce qui nous concerne) les indices commencent toujours à 0 (le premier élément de la séquence a pour indice 0)

y = coordonnees[1]

Les listes¶

Le type list en python est un tableau (array en anglais) dynamique. Contrairement aux tuples, les listes sont muables (ou "mutables"), c'est à dire qu'on peut modifier leur contenu.

    notes = [1, 20, 10, 15]

Notez l'utilisation de crochets à la place des parenthèses.

Comme pour les tuples on récupère un élément en utilisant un indice.

Question

En se basant sur les tuples, pouvez vous dire quelle note sera récupérée en exécutant le code ci-dessous ?

    note = notes[1]

On peut modifier un élément de la liste :

    note[0] = 20

Question

Quelle sera l'état de la liste après cette modification ?

Pour ajouter un élément au tableau on peut utiliser la méthode append :

    notes.append(12)

Il est possible de mélanger dans une même liste des variables de types différents. L'insctruction ci-dessous est donc valide en Python.

    notes.append('A')

On peut également ajouter une liste à une liste :

    nom = ['riri', 'fifi']
    nom.append(['loulou'])

Donnera comme résultat :

['riri', 'fifi', ['loulou']]

Parcourir les éléments¶

Il est possible de compter le nombre d'entrées d'une liste avec la fonction len.

Il existe des manières très différentes de balayer tous les éléments d'une liste Python (le principe est le même pour les tuples).

La première consiste à lire tous les éléments en les appelant par leur index. On fera donc une boucle allant de 0 jusqu'à la longueur de la liste moins 1 et de lire les éléments en les appelants avec leur index.

notes = [1, 19, 15, 16]

for i in range(len(notes)) :
    print(notes[i])

La deuxième méthode est de réaliser une itération sur l'ensemble de éléments de la liste. On utilise cette méthode lorsque l'on n'a pas besoin de connaitre la position de l'élément dans la liste.

notes = [1, 19, 15, 16]

for note in notes :
    print(note)

Supprimer les éléments d'une liste¶

Supprimer une entrée d'une liste avec son index :¶

Il est parfois nécessaire de supprimer une entrée de la liste. Pour cela vous pouvez utiliser la fonction del.

Question

Quel sera d'après vous l'état de la liste après l'exécution de la fonction del ? notes = [1, 19, 15, 16] del notes[0]

Supprimer une entrée avec sa valeur :¶

On peut également supprimer une entrée d'une liste à partir de sa valeur en utilisant la méthode remove() :

notes = [1, 19, 15, 16]
notes.remove(19)

Ci-dessous on a supprimé la note 19.

Slicing¶

Le slicing (saucissonage) permet d’obtenir une sous-liste depuis une liste.

La syntaxe globale d’une tranche est : [début: fin: pas] Chacun des arguments est optionnel. Attention, la valeur de fin n'est jamais comprise.

A noter qu'il est souvent utile de récupérer la dernière valeur en utilisant l'indice -1.

Listes en compréhension¶

La dernière notion à présenter est la compréhension de listes, qui permettent la création de listes de manière très concise et très proche des notations ensemblistes utilisées en mathématiques.

On souhaite construire une liste contenant les carrés des nombres entiers positifs de 0 à 10. On opterait naturellement pour la construction suivante :

carres = []
for i in range(11) :
    carres.append(i**2)

En utilisant les compréhensions de listes, on obtiendrait exactement le même résultat en utilisant le code suivant :

carres = [i**2 for i inrange(11)]

Introduction à la complexité¶

Nous allons par la suite étudier la notion de complexité en temps qui est un peu abstraite. Profitons donc d'une problématique simple sur les séquences pour introduirez ce concept.

Question

Supposons que je dispose d'un tableau avec \(n\) éléments, et que je cherche un élément en particulier (par exemple la note 20 dans notre liste de notes).

A chaque itération (c'est à dire à chaque fois que je visite une note dans la liste de notes) j'effectue une opération de comparaison pour vérifier si cette note est bien celle que je cherche (note == 20 par exemple).

Lorsque j'ai 5 notes :

notes = [20, 2, 3, 5, 19]

Dans le pire des cas (celui où j'effectue le plus de comparaisons), combien de fois devrais je comparer les notes avant de trouver celle que je cherche ?
Plus généralement si j'ai \(n\) notes alors dans le pire des cas combien d'opérations de comparaison devrait je effectuer ?

Nous venons d'introduire la complexité linéaire, notée \(O(n)\).

A votre avis, pourquoi parle t'on dans ce cas de complexité linéaire ?