Physique, Chimie et Informatique > Terminales Spé. NSI
Structures de données fournies avec le langage Python
Au programme
Contenus
Capacités attendues
Commentaires
- Structures de données, interface et implémentation.
- Spécifier une structure de données par son interface. - Distinguer interface et implémentation. - Écrire plusieurs implémentations d’une même structure de données.
L’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles).
- Dictionnaires, index et clé.
- Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire.
Structures de données fournies avec le langage Python
Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace.
Rappels : modules, fonctions
À retenir
Pour chaque module, on distingue :
sa réalisation (ou implémentation) : c’est le code lui-même.
son interface (API) : c’est l’énumération des fonctions définies dans le module qui sont utilisées depuis d’autres modules/programmes, les clients.
L’interface doit présenter une documentation dans laquelle tout ce que doit savoir le client doit être indiqué.
L’objectif de l’interface est que le client n’ait pas à consulter l’implémentation pour utiliser les fonctions.
Avertissement
L’interface peut être envisagée comme une abstraction du module : une description de ce qui caractérise ce module sans jamais entrer dans les détails de l’implémentation.
À retenir
Pour chaque fonction du module, la spécification doit indiquer :
son nom.
la liste de ses paramètres accompagnés de leur type.
le type de la valeur retournée.
la documentation de la fonction.
Avertissement
La spécification peut être envisagée comme une abstraction de la fonction : une description de ce qui caractérise cette fonction sans jamais entrer dans les détails de l’implémentation.
Avantages d’une barrière d’abstraction
Séparation du programme en deux composantes : Implémentation et code client.
La barrière d’abstraction permet de faire varier l’implémentation sans impacter le client.
La barrière d’abstraction permet de cacher (encapsuler) le code de l’implémentation.
Pourquoi différentes structures de données ?
Les structures de donnéesorganisent différemment les données que le programme traite. Le langage Python fournissant le type list, on pourrait se demander pourquoi ne pas systématiquement l’utiliser et pourquoi devoir apprendre de nouveaux types.
En fait, la spécialisation des structures de données rend la programmation plus simple (utilisation de l’API) et plus efficace (complexité).
Avertissement
Nous verrons dans les prochains chapitres qu’il faut distinguer l’objet que l’on manipule dans un programme de son implémentation (comment il est programmé).
À retenir
Un même type peut être implémenté de différentes façons. Dans tous les cas, il présente la même interface au programmeur (API).
On parle donc de type abstrait.
Principaux types abstraits fournis avec le langage Python
Liste : list
Le type list de Python n’est pas implémenté à l’aide de listes chaînées (que nous étudierons au chapitre 7), car la suppression ou l’ajout ailleurs qu’en fin de liste nécessite de décaler les valeurs de fin de liste, et n’est donc pas réalisé en temps constant. D’autre part, l’accès à un élément quelconque est réalisé en temps constant, ce qui n’est pas le cas avec une liste chaînée.
Le type list de Python est implémenté à l’aide de tableaux dynamiques.
Tableau associatif : dict
Le type dict de Python est une implémentation du type abstrait tableau associatif. L’implémentation correspond à une table de hachage, ce qui signifie que la valeur est stockée dans un tableau et que la position dans ce tableau dépend du résultat d’une fonction de hachage appliquée à la clé. En un temps indépendant du nombre de valeurs stockées dans le dictionnaire, Python peut retrouver la valeur associée à n’importe quelle clé : pour cela il calcule un indice à partir de la valeur de la clé (qui doit donc être hachable, c’est-à-dire récursivement non mutable) et récupère la valeur stockée à cet indice dans un tableau.
Une caractéristique essentielle des dictionnaires est que la récupération d’une valeur associée à une clé se fait en un temps constant, indépendant de la taille du dictionnaire. De même, savoir si une clé fait partie du dictionnaire prend un temps constant (alors que vérifier si un élément est dans une liste prend un temps proportionnel à la taille de la liste).
Ensemble : set
Un ensemble Python (set) est équivalent à un dictionnaire ne contenant que des clés. Par construction, chaque élément est donc unique. De plus, avec le type set on dispose déjà des opérations ensemblistes habituelles, implémentées de manière très efficace : union, intersection, différence, etc.
Opérations usuelles et complexité en temps
Opérations sur les listes
Type Python
Implémentation
Opération
Exemple
Complexité
list
Tableau dynamique
Ajout à la fin
lst.append(x)
O(1)
lst=[]
Accès à un élément
lst[i]
O(1)
len(lst)
Modification d’un élément
lst[i] = x
O(1)
Effacement d’un élément
del lst[i]
O(n)
Insertion d’un élément
lst.insert(i, x)
O(n)
Recherche d’un élément
x in lst
O(n)
Opérations sur les dictionnaires
Type Python
Type abstrait
Opération
Exemple
Complexité
dict
Tableau associatif
Ajout d’un élément
d[key] = val
O(1)
d={}
Modification d’un élément
d[key] = val
O(1)
len(d)
Effacement d’un élément
del d[key]
O(1)
Accès à un élément
d[key]
O(1)
Recherche d’une clé
key in d
O(1)
Recherche d’une valeur
val in d.values()
O(n)
Opérations sur les ensembles
Type Python
Type abstrait
Opération
Exemple
Complexité (moyenne)
set
Ensemble
Ajout d’un élément
s.add(elt)
O(1)
s = {}
Retrait d’un élément
s.remove(elt)
O(1)
len(s)
Test d’appartenance
elt in s
O(1)
Union
s | t
O(n+m)
Intersection
s & t
O(min(n,m))
Différence
s - t
O(n)
Différence symétrique
s ^ t
O(n)
Exemple : Définition et implémentation du type abstrait « Liste » à l’aide de tableaux dynamiques en Python
Interface du type abstrait « Liste »
L’interface de la classe est la suivante :
HelponclassListeinmodule__main__:classListe(builtins.object)|Liste()->'None'||Classeimplémentantletype«Liste»,|versiontrèssimplifiéedutype«liste»dePython.||Methodsdefinedhere:||__getitem__(self:'TableauDynamique',i:'int')->'object'|Retournel'élément d'indicei.||__init__(self:'TableauDynamique')->'None'|Créationd'un tableau vide à l'initialisation.||__len__(self:'TableauDynamique')->'int'|Retournelenombred'éléments dans le tableau.||append(self:'TableauDynamique',obj:'object')->'None'|Ajoutel'élément obj en dernière position dans le tableau.
Implémentation
Créer la classe Liste.
Dans la méthode __init__, initialiser trois attributs privés _nbre, _capacite et _tab tels que _nbre donne le nombre d’éléments dans le tableau (initialement égal à 0), _capacite donne le nombre maximal possible d’éléments dans le tableau (initialement égal à 1) et _tab référence un tableau créé à l’aide de la fonction py_object du module ctypes.
Remarque : le code de création du tableau est le suivant :
def_construit_tableau(self:Liste,capacite:int):"""
Construction d'un tableau de capacité donnée.
"""return(capacite*ctypes.py_object)()
Définir la méthode __len__ dont la spécification est :
def__len__(self:Liste)->int:"""
Retourne le nombre d'éléments dans le tableau.
"""
Définir la méthode __getitem__ dont la spécification est :
def__getitem__(self:Liste,i:int)->object:"""
Retourne l'élément d'indice i.
Une exception est levée si l'indice n'appartient
pas au bon intervalle.
"""
Définir la méthode privée _augmente_taille dont la spécification est :
def_augmente_taille(self:Liste,capacite:int)->None:"""
Crée un nouveau tableau de dimension capacite puis copie tous les
éléments de l'ancien tableau dans ce dernier.
Fait en sorte que le nouveau tableau soit le tableau désormais
utilisé.
Met à jour l'attribut capacite.
"""
Définir la méthode append dont la spécification est :
defappend(self:Liste,obj:object)->None:"""
Ajoute l'élément obj en dernière position dans le tableau.
"""
Remarque : La méthode append doit appeler la méthode _augmente_taille.
Définir la méthode __repr__ dont la spécification est :
def__repr__(self:Liste)->str:"""
Retourne la chaîne de caractères représentant le tableau.
"""
Tester le bon fonctionnement de la classe.
Corrigé
from__future__importannotationsimportctypesclassListe:"""
Implémentation du type abstrait liste avec des
tableaux dynamiques.
"""def__init__(self:Liste)->None:"""
Initialisation de l'objet
"""self._nbre=0# Nbre d'éléments dans la listeself._capacite=1# Nbre max d'éléments dans le tableauself._tab=self._construit_tableau(self._capacite)# Tableaudef_construit_tableau(self:Liste,capacite:int):"""
Construction d'un tableau de capacité donnée.
"""return(capacite*ctypes.py_object)()def__len__(self:Liste)->int:"""
Retourne le nombre d'éléments dans le tableau.
"""returnself._nbredef__getitem__(self:Liste,i:int)->object:"""
Retourne l'élément d'indice i.
Une exception est levée si l'indice n'appartient
pas au bon intervalle.
"""ifi>=self._nbre:raiseIndexError("Indice trop grand !")elifi<0:i=self._nbre+ireturnself._tab[i]def_augmente_taille(self:Liste,capacite:int)->None:"""
Crée un nouveau tableau de dimension capacite puis copie
tous les éléments de l'ancien tableau dans ce dernier.
Fait en sorte que le nouveau tableau soit le tableau désormais
utilisé.
Met à jour l'attribut capacite.
"""new_tab=self._construit_tableau(capacite)foriinrange(self._nbre):# new_tab[i] = self._tab.__getitem__(i)new_tab[i]=self._tab[i]self._tab=new_tabself._capacite=capacitedefappend(self:Liste,obj:object)->None:"""
Ajoute l'élément obj en dernière position dans le tableau.
"""ifself._nbre==self._capacite:self._augmente_taille(2*self._capacite)self._tab[self._nbre]=objself._nbre+=1def__repr__(self:Liste)->str:"""
Retourne la chaîne de caractères représentant le tableau.
"""chaine="["foriinrange(self._nbre):chaine+=str(self._tab[i])ifi!=self._nbre-1:chaine+=", "chaine+="]"returnchaineif__name__=="__main__":liste=Liste()print(f"Longueur de la liste : {len(liste)}")print(f"Capacité du tableau : {liste._capacite}")liste.append(3)# TableauDynamique.append(liste, 3)print(f"Longueur de la liste : {len(liste)}")print(f"Capacité du tableau : {liste._capacite}")print(liste)foriinrange(112):liste.append(i)print(f"Longueur de la liste : {len(liste)}")print(f"Capacité du tableau : {liste._capacite}")print(liste)
Physique, Chimie et Informatique > Terminales Spé. NSI > Structures de données fournies avec le langage Python
Au zoo de Beauval, il y a 5 éléphants d’Asie, 17 écureuils d’Asie, 2 pandas d’Asie, etc.
On représente cet inventaire à l’aide d’un dictionnaire, de façon suivante :
On souhaite se doter d’une fonction plus_grand_nombre() qui prend un zoo en paramètre et qui renvoie le nom de l’animal le plus représenté dans ce zoo.
Par exemple
Quel type de boucle peut-on envisager pour le code de cette fonction ?
for cle in dico.keys()
for valeur in dico.values()
for (cle, valeur) in dico.items()
Aucune boucle.
Écrire le corps de cette fonction.
On souhaite se doter d’une fonction nombre_total qui prend un zoo en paramètre ainsi que le nom d’un continent, et qui renvoie le nombre d’animaux originaires de ce continent dans le zoo.
Par exemple :
Quel type de boucle peut-on envisager pour le code de cette fonction ?
for cle in dico.keys()
for valeur in dico.values()
for (cle,valeur) in dico.items()
Aucune boucle.
Écrire le code de cette fonction.
On souhaite se doter d’une fonction nombre qui prend un zoo en paramètre ainsi que le nom d’un animal, et qui renvoie le nombre de représentants de cet animal dans le zoo.
Par exemple :
Quel type de boucle peut-on envisager pour le code de cette fonction ?
for cle in dico.keys()
for valeur in dico.values()
for (cle,valeur) in dico.items()
Aucune boucle.
Écrire le code de cette fonction.
Solution
fromtypingimportDict,Tupledefplus_grand_nombre(zoo:Dict[str,Tuple[str,int]])->str:"""
Retourne le nom de l’animal le plus représenté dans le zoo.
"""nbre_max=0# nbre maximale d'animauxforcle,valeurinzoo.items():ifvaleur[1]>nbre_max:nbre_max=valeur[1]cle_max=cleelifvaleur[1]==nbre_max:cle_max+=", "+clereturncle_maxdefnbre_total_continent(zoo:Dict[str,Tuple[str,int]],continent:str)->int:"""
Retourne le nombre d’animaux originaires de ce continent dans le zoo.
"""nbre_total=0# Nbre total d'animaux pour le continentforvaleurinzoo.values():ifvaleur[0]==continent:nbre_total+=valeur[1]returnnbre_totaldefnbre_pour_animal(zoo:Dict[str,Tuple[str,int]],animal:str)->int:"""
Retourne le nombre de représentants de animal dans zoo.
"""ifanimalinzoo.keys():rep=zoo[animal][1]else:# si animal pas présent dans zoorep=0returnrepif__name__=="__main__":zoo_Beauval={"éléphant":("Asie",5),"écureuil":("Asie",17),"panda":("Asie",2),"hippopotame":("Afrique",7),"girafe":("Afrique",4),"lion":("Afrique",17),}zoo_LaFleche={"ours":("Europe",4),"tigre":("Asie",7),"girafe":("Afrique",11),"hippopotame":("Afrique",3),}assertplus_grand_nombre(zoo_LaFleche)=="girafe"assertplus_grand_nombre(zoo_Beauval)=="écureuil, lion"assertnbre_total_continent(zoo_LaFleche,"Afrique")==14assertnbre_total_continent(zoo_Beauval,"Asie")==24assertnbre_pour_animal(zoo_Beauval,"panda")==2assertnbre_pour_animal(zoo_LaFleche,"panda")==0