Types avancés : listes dynamiques, ensembles, dictionnaires⚓︎
La lecture de la section sur les listes dynamiques pourra être utile en mathématiques, on les rencontre souvent. Nous allons cependant montrer que l'on peut parfois s'en passer grâce aux listes en compréhension.
On recommande donc à tous la lecture de la partie sur « Listes dynamiques », pour apprendre à en avoir moins besoin en mathématiques au lycée.
La suite est pour les élèves de première en NSI, ou les curieux.
Les listes dynamiques⚓︎
On a déjà évoqué que la structure de données élémentaire, dans presque tous les langages de programmation, utilisée pour stocker en ligne des éléments de même nature est le tableau.
Un tableau :
- a une taille fixe définie à la création,
- a ses éléments de même nature, modifiables.
Le type list
de Python permet de travailler de cette manière, mais offre en plus les possibilités :
- de faire varier la taille de la liste, en n'importe quel endroit,
- d'avoir des éléments de nature différente, mais nous ne le recommandons pas.
Les méthodes dynamiques utilisent la notation de la programmation orientée objet, avec un .
qui indique à gauche le parent et à droite la filiation.
Ajout d'élément à une liste⚓︎
À une liste, on peut ajouter un élément.
>>> une_liste = [2, 3, 5, 7]
>>> une_liste.append(11)
>>> une_liste
[2, 3, 5, 7, 11]
>>>
.append()
sert à ajouter à la liste citée juste avant le .
qui indique la filiation.
Exemple d'utilisation⚓︎
Prenons un exemple volontairement simple, écrit avec deux styles différents que nous allons comparer.
def carrés_pairs(ma_liste):
"Renvoie la liste des carrés pairs des éléments de `ma_liste`"
résultat = list() # variante de `résultat = []` ; pour une liste vide
for x in ma_liste:
carré = x * x
if carré % 2 == 0:
résultat.append(carré)
return résultat
On rappelle qu'on préfère les listes en compréhension avec le code suivant :
def carrés_pairs(ma_liste):
"Renvoie la liste des carrés pairs des éléments de `ma_liste`"
return [x * x for x in ma_liste if x * x % 2 == 0]
Cependant, on constate qu'avec les listes en compréhension, on fait deux fois le calcul x * x
pour chaque cas validé ; cela pourrait être gênant et lent, d'autre part le code n'est pas factorisé... Dans cet exemple, nous pourrions connaître la parité de x * x
sans calculer x * x
, c'est juste un exemple simple d'illustration.
La méthode
.append()
est parfois très utile, mais parfois uniquement pour de l'optimisation.
En mathématiques au lycée, on essayera donc de limiter l'utilisation de ces méthodes dynamiques, et de plutôt travailler avec les listes en compréhension.
La suite de cette page est donnée à titre d'information et ne devrait pas être utilisée en mathématiques. En revanche, elle intéressera les élèves de NSI.
Autres méthodes d'une liste⚓︎
ma_liste.sort()
trie en place la listema_liste
ma_liste.reverse()
renverse en placema_liste
ma_liste.index(élément)
renvoie l'indice deélément
dansma_liste
; s'il est absent, une erreur survient.ma_liste.extend(autre_liste)
prolongema_liste
avecautre_liste
ma_liste.remove(élément)
enlèveélément
(le premier trouvé) dema_liste
ma_liste.insert(élément, indice)
ajouteélément
à l'indice
préciséma_liste.pop()
renvoie en supprimant le dernier élément dema_liste
Pour découvrir toutes les méthodes d'un
objet
python, on utilisedir(objet)
, et ensuite pour avoir de l'aide sur uneméthode
on entrehelp(objet.méthode)
>>> ma_liste = [2, 3, 5, 7]`
>>> dir(ma_liste)
['__add__', '__class__', '__contains__', '__delattr__',
'__delitem__', '__dir__', '__doc__', '__eq__',
'__format__', '__ge__', '__getattribute__', '__getitem__',
'__gt__', '__hash__', '__iadd__', '__imul__', '__init__',
'__init_subclass__', '__iter__', '__le__', '__len__',
'__lt__', '__mul__', '__ne__', '__new__', '__reduce__',
'__reduce_ex__', '__repr__', '__reversed__', '__rmul__',
'__setattr__', '__setitem__', '__sizeof__', '__str__',
'__subclasshook__',
'append', 'clear', 'copy', 'count', 'extend', 'index',
'insert', 'pop', 'remove', 'reverse', 'sort']
>>> help(ma_liste.count)
Help on built-in function count:
count(value, /) method of builtins.list instance
Return number of occurrences of value.
- On découvre qu'il y a de nombreuses méthodes privées, celles dont le nom est entouré de
__
. - On découvre l'aide sur
.count()
: renvoie le nombre d'occurrences d'une valeur.
More about Python list ; en anglais
Bonne pratique
Avant la programmation orientée objet, on utilisait une écriture du genre ajoute(élément, ma_liste)
ou alors ajoute(ma_liste, élément)
; aucune des deux n'est satisfaisante, et les choses se compliquent lorsqu'on travaille avec des méthodes plus complexes encore...
Avec la notation objet.méthode(paramètre)
le concept est plus clair !
Les ensembles⚓︎
Un ensemble (set de type set
) est un objet Python mutable qui possède des éléments sans doublon, et sans ordre.
- On ne peut pas dire qui est l'élément d'indice
i
donné. - Si on ajoute un élément déjà présent, il n'est pas ajouté une seconde fois.
- Les éléments d'un ensemble doivent être immuables, par exemple on peut avoir des nombres, ou des chaînes de caractères, ou bien des tuples, mais pas de listes ni d'ensembles.
L'utilisation des ensembles ressemble à celle des listes dynamiques, avec des méthodes de programmation orientée objet.
Remarque (hors programme) : il est possible de créer un ensemble figé, donc immuable, avec
frozenset
. Ainsi les listes et les ensembles ont leur version immuable :tuple
etfrozenset
.More about Python set ; en anglais
Construction⚓︎
set()
pour un ensemble videset(i*i%10 for i in range(10))
définition en compréhension, ou bien{i*i%10 for i in range(10)}
set(ma_liste)
pour renvoyer une version sans doublon, ni ordre, d'une liste. La fonctionset()
essaie de transformer son argument en ensemble.
⚠️ l'ensemble vide se définit avec
set()
, mais s'affiche comme{}
, or définir avec{}
donne un dictionnaire vide ; danger, c'est différent.
Exemples⚓︎
>>> {n * n % 10 for n in range(100)}
{0, 1, 4, 5, 6, 9}
>>> set("Bonjour")
{'r', 'j', 'B', 'u', 'o', 'n'}
>>>
- Les éléments ne sont pas, a priori, triés.
- Il n'y a pas de doublon.
Les méthodes des ensembles⚓︎
Donnons seulement les principales, pour les autres, voir dir(set())
On suppose que truc
est un ensemble Python
truc.add(élément)
ajoute l'élément
à truc, sans doublon, ni ordre.truc.remove(élément)
enlèveélément
àtruc
; provoque une erreur si absent.
Les fonctions sur les ensembles⚓︎
Comme pour les listes, on a les fonctions suivantes pour truc
un ensemble (de type set
donc) :
len(truc)
renvoie le nombre d'éléments detruc
x in truc
renvoie un booléen,True
six
est danstruc
, sinonFalse
max(truc)
renvoie le maximum detruc
s'il est non videmin(truc)
renvoie le minimum detruc
s'il est non videsum(truc)
renvoie la somme des éléments detruc
; erreur sitruc
contient des éléments non numériques.
Les dictionnaires⚓︎
Le principe d'un dictionnaire est de créer, comme pour un tableau, une association entre des clés et des valeurs.
- Dans un tableau
tab
de taille \(n\), les clés sont les indicesi
de \(0\) inclus à \(n\) exclus. On notetab[i]
la valeur associée à l'indicei
. - Dans un dictionnaire
dico
, les clés peuvent être tout objetclé
, et la valeur associée est référencée avecdico[clé]
, avec le même style que pour les tableaux, donc.
Utilisations simples⚓︎
- Pour créer un dictionnaire vide, on entre
mon_dico = dict()
- On pourrait aussi utiliser
mon_dico = {}
, mais cela peut donner une confusion avec l'ensemble vide...
- On pourrait aussi utiliser
- Pour ajouter ou modifier une association clé-valeur, on entre
mon_dico[ma_clé] = ma_valeur
. - Pour créer un dictionnaire non vide, on peut faire comme l'exemple ci-dessous. (Remarque, on peut écraser une association clé-valeur si elle existait déjà avant.)
# codé en dur
longueur_mot = {'pour': 4, 'créer': 5, 'un': 2, 'dictionnaire': 12}
# avec une boucle
phrase = "pour créer un dictionnaire"
longueur_mot = dict()
for mot in phase.split():
longueur_mot[mot] = len(mot)
# avec une compréhension
phrase = "pour créer un dictionnaire"
longueur_mot = {mot: len(mot) for mot in phrase.split()}
Exemples de dictionnaires⚓︎
Pour traduire des mots⚓︎
>>> traduction_fr_en = {'mot': 'word', 'virgule' : 'coma', 'phrase' : 'sentence', 'point': 'point'}
>>> traduction_fr_en['phrase']
'sentence'
>>> traduction_fr_en['lettre']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'lettre'
Pour stocker des numéros⚓︎
Voici un script qui enregistre des numéros de cartes pour une classe.
def inscrire_élèves(nb_élèves):
num_carte = dict()
for _ in range(nb_élèves):
nom = input('Quel est votre nom ?')
numéro = input('Quel est votre numéro de carte ?')
num_carte[nom] = numéro
return num_carte
Pour mémoriser des résultats⚓︎
On suppose que l'on a une fonction f
dont le calcul coûte cher pour certaines entrées que l'on appelle souvent.
- Si les entrées sont des petits entiers alors un tableau est idéal pour stocker les valeurs associées à l'entrée qui sera l'indice du tableau. On peut initialiser le tableau rempli de
None
pour désigner le fait que la fonction n'a pas encore été calculée. - Sinon, on peut utiliser un dictionnaire.
Version avec un tableau
# on suppose f est une fonction à un paramètre entier x
# On va utiliser un tableau pour stocker certaines valeurs
tab_taille = 10000
f_tab = [None for _ in range(tab_taille)]
def f_mem(x):
if 0 <= x < tab_taille:
if f_tab[x] is None:
f_tab[x] = f(x)
return f_tab[x]
else:
return f(x)
Version avec un dictionnaire
# on suppose f est une fonction à un paramètre entier x
# On va utiliser un dictionnaire pour stocker certaines valeurs
f_dico = dict()
def f_mem(x):
if x not in f_dico:
f_dico[x] = f(x)
return f_dico[x]
Le code est bien plus simple, inutile de faire des suppositions sur l'entrée. C'est une excellente pratique. On la trouve souvent avec la dénomination de mémoïsation.
Itérer avec un dictionnaire⚓︎
On fera comme s'il n'y avait pas d'ordre pour les clés, et que l'on peut itérer sur les différentes clés d'un dictionnaire avec le code :
for une_clé in mon_dico:
ma_fonction(mon_dico[une_clé])