Aller au contenu

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 liste ma_liste
  • ma_liste.reverse() renverse en place ma_liste
  • ma_liste.index(élément) renvoie l'indice de élément dans ma_liste ; s'il est absent, une erreur survient.
  • ma_liste.extend(autre_liste) prolonge ma_liste avec autre_liste
  • ma_liste.remove(élément) enlève élément (le premier trouvé) de ma_liste
  • ma_liste.insert(élément, indice) ajoute élément à l'indice précisé
  • ma_liste.pop() renvoie en supprimant le dernier élément de ma_liste

Pour découvrir toutes les méthodes d'un objet python, on utilise dir(objet), et ensuite pour avoir de l'aide sur une méthode on entre help(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 et frozenset.

More about Python set ; en anglais

Construction⚓︎

  • set() pour un ensemble vide
  • set(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 fonction set() 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 de truc
  • x in truc renvoie un booléen, True si x est dans truc, sinon False
  • max(truc) renvoie le maximum de truc s'il est non vide
  • min(truc) renvoie le minimum de truc s'il est non vide
  • sum(truc) renvoie la somme des éléments de truc ; erreur si truc 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 indices i de \(0\) inclus à \(n\) exclus. On note tab[i] la valeur associée à l'indice i.
  • Dans un dictionnaire dico, les clés peuvent être tout objet clé, et la valeur associée est référencée avec dico[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...
  • 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é])