Pour représenter des structures de données, Python propose quatre types de base: les listes (type list), les tuples (type tuple), les ensembles (type set) et les dictionnaires (type dict). Le but de ce chapitre est de montrer les différences fondamentales entre ces structures de données et d'expliquer à quoi elles sont le plus adaptées. La documentation détaillée sur les structures de données est disponible ici.

Exercice 2.1: Listes

Une liste est une structure permettant de stocker des éléments hétérogènes:

list0 = [0, 5.4, "chaîne", True]

Les listes sont mutables, c'est-à-dire qu'il est possible d'y modifier un élément, d'en rajouter un ou d'en supprimer un sans avoir à redéfinir toute la liste.

list0[3] = False # remplace True par False
list0.append("nouveau") # ajoute la chaîne de caractères "nouveau" à la liste
list0.insert(2, 34) # insère 34 à la place 2
list0.remove(0) # enlève 0

En particulier, il faut faire attention en copiant une liste. Si l'on exécute le code suivant:

list1 = list0
list1[2] = "change"
list0

alors list0 est aussi modifié et est égal à list1. En effet, exécuter list1 = list0 ne crée pas un nouvel objet (dans la mémoire vive de l'ordinateur), mais crée simplement une autre variable pointant vers le même objet. Pour le vérifier, il est possible d'utiliser la command id qui renvoie l'identifiant unique d'une variable : si deux variables ont le même identifiant, alors elles pointent vers le même objet. C'est le cas avec le code list1 = list0:

id(list0) == id(list1)

Pour créer une vraie copie, il faut utiliser la méthode copy:

list2 = list0.copy()
list2[2] = "rechange"
list0

qui ne modifie pas list0. À noter qu'il est possible de modifier les éléments d'une liste à l'intérieur d'une fonction:

def f(l):
    l[0] = 0
f(list0)

Enfin il est possible de créer des listes à l'aide de la compréhension de listes:

list1 = [2*i+1 for i in range(10)]

a) Chercher dans la documentation la syntaxe pour concaténer deux listes.

Indication

b) Chercher dans la documentation la syntaxe pour extraire une tranche d'une liste, c'est-à-dire: si a est par exemple une liste de longueur 10, retourner les éléments de 6 à 9.

Indication

c) Chercher dans la documentation la syntaxe pour retourner la longueur d'une liste.

d) Écrire une fonction fibonacci(N) qui retourne la liste des \( N\geq2 \) premiers termes de la suite de Fibonacci définie par \( u_{n+2} = u_{n+1}+u_n \) avec \( u_0=0 \) et \( u_1=1 \).

e) Écrire une fonction pascal(N) qui retourne la \( N \)-ième ligne du triangle de Pascal:

f) Soit les suites \( (u_n)_{n\in\mathbb{N}} \) et \( (v_n)_{n\in\mathbb{N}} \) définies par \( u_0=1 \), \( v_0=1 \), et $$ \begin{align*} u_{n+1} &= u_n + v_n \,, & v_{n+1} &= 2u _n - v_n \,, \end{align*} $$ pour \( n\geq0 \). Calculer \( u_{100} \) et \( v_{100} \).

Réponse

g) Écrire une fonction vk(n0,K), qui pour deux entiers \( n_0 \) et \( K\geq1 \) calcule la suite des valeurs \( v_k \) définies par \( v_0 = n_0 \) et $$ v_{k+1}=\begin{cases} 3v_{k}+1 & \text{si $v_{k}$ est impair},\\ \frac{v_{k}}{2} & \text{si $v_{k}$ est pair}, \end{cases} $$ pour \( 0 \leq k < K \). Pour \( K = 1 000 \) et diverses valeurs de \( n_0 \in \{10, 100, 1 000, 10 000\} \), afficher les cinq dernières valeurs calculées, c'est-à-dire \( (v_{K-4},v_{K-3},v_{K-2},v_{K-1},v_K) \).

Réponse

vk(10,1000) == [1, 4, 2, 1, 4]
vk(100,1000) == [2, 1, 4, 2, 1]
vk(1000,1000) == [1, 4, 2, 1, 4]
vk(10000,1000) == [4, 2, 1, 4, 2]

Exercice 2.2: Tuples

Les tuples permettent tout comme les listes de stocker des éléments hétérogènes:

tuple0 = (0, 5.4, "chaîne", True)

Mais au contraire des listes, les tuples ne sont pas mutables. Il n'est pas possible d'y modifier un élément, d'en rajouter un ou d'en supprimer un sans redéfinir tout le tuple. L'avantage d'un tuple sur une liste est qu'il est hashable, ce qui implique qu'il peut être utilisé comme clef dans un dictionnaire ou inclus dans un ensemble.

Une fonction de hachage est une fonction injective permettant de calculer un identifiant unique pour chaque entrée, et donc de vérifier si deux entrées sont identiques en comparant leurs identifiants, ce qui est beaucoup plus rapide que de comparer toutes les entrées. Une fonction de hashage ne peut s'appliquer que sur des éléments pas mutables car sinon il faudrait modifier l'identifiant à chaque modification de l'élément.

Enfin il est possible d'affecter des variables à l'intérieur d'un tuple, par exemple:

(a,b) = (1,9)

Cela est en particulier très utile pour échanger deux variables sans avoir à utiliser une variable supplémentaire:

(a,b) = (b,a)

a) Vérifier qu'un tuple est bien immutable.

b) Définir une fonction mdlast(lst,val) ayant pour argument une liste de tuples d'entiers lst et un entier val et retourner la liste de tuples avec le dernier élément de chaque tuple remplacé par val. Par exemple si lst = [(10, 20), (30, 40, 50, 60), (70, 80, 90)] alors mdlast(lst,100) doit retourner [(10, 100), (30, 40, 50, 100), (70, 80, 100)].

c) Comment convertir un tuple en liste et réciproquement ?

Exercice 2.3: Ensembles

Les ensembles permettent de stocker des éléments hétérogènes au sens mathématique de la théorie des ensembles:

set0 = {0, 5.4, "chaîne", True}

Il est possible de tester si un élément appartient à un ensemble:

if "chaîne" in set0:
    print("dedans")

Les ensembles sont mutables, il est donc possible de rajouter ou retirer un élément d'un ensemble:

set0.add(18) # ajoute 18 à l'ensemble
set0.add(0) # ajoute 0 à l'ensemble (ne fait rien car 0 est déjà dedans)
set0.remove("chaîne") # retire "chaîne de l'ensemble

En revanche les ensembles ne peuvent contenir que des éléments hashables, c'est-à-dire immutables. La raison est que les ensembles utilisent des tables de hachage permettant de calculer très rapidement si un élément est présent dans un ensemble, bien plus rapidement que dans une liste ou un tuple. En particulier un ensemble ne peut pas contenir un autre ensemble:

set1 = {{1,2},{3},{4}}
TypeError: unhashable type: 'set'

À noter qu'il existe également en Python des ensembles immutables frozenset:

frozenset0 = frozenset([0, 5.4, "chaîne", True])

Une chaîne de caractères peut être transformée en ensemble:

set1 = set('abracadabra')

Comme pour les listes, il est possible de faire des compréhensions d'ensembles:

set2 = {x for x in 'abracadabra' if x not in 'abc'}

Dans cet exemple les chaînes de caractères sont automatiquement transformées en ensemble. À noter que l'ensemble vide est défini par set().

a) Définir une fonction divisible(n) qui retourne l'ensemble des nombres entiers divisibles par n inférieurs ou égaux à 100.

b) Chercher dans la documentation comment faire l'intersection, l'union, et la différence de deux ensembles. Déterminer les nombres inférieurs ou égaux à 100 qui sont non divisibles par 2 mais divisibles par 3 et 5.

Indication

Exercice 2.4: Dictionnaires

Les dictionnaires sont une structure permettant de stocker des éléments hétérogènes indexés par des clefs (elles aussi hétérogènes):

dict0 = {"pommes": 0, "poires": 4, 12: 2}

Les éléments d'un dictionnaire sont accessibles par les clefs:

dict0["pommes"]
dict0[12]

Un dictionnaire peut être vu comme un tableau associatif associant à chaque clef une valeur. La liste des clefs et celle des valeurs sont accessibles respectivement avec dict0.keys() et dict0.values(). Les dictionnaires sont mutables, il est donc possible de modifier une association clef-valeur et d'en rajouter ou supprimer une:

dict0["pommes"] = 3 # modifie la valeur associée à pommes
dict0["oranges"] = "beaucoup" # rajoute oranges comme clef avec la valeur "beaucoup"
del dict0["poires"] # supprime le couple clef-valeur associé à poires
dict0.pop("pommes") # supprime le couple clef-valeur associé à pommes

Bien qu'un dictionnaire soit mutable, les clefs qui le composent doivent être des objets hashables, c'est-à-dire immutables. La raison est que Python utilise une fonction de hashage sur les clefs pour des questions de performance. Ainsi une liste ou un ensemble ne peuvent pas servir de clefs dans un dictionnaire:

dict0[list0] = "test"
TypeError: unhashable type: 'list'
dict0[set0] = "retest"
TypeError: unhashable type: 'set'

En revanche il est possible d'avoir un tuple ou un frozenset comme clef:

dict0[tuple0] = "test"
dict0[frozenset0] = "rest"

d'où l'intérêt des frozensets. Comme pour les listes et les ensembles, il est possible de faire des compréhensions de dictionnaires:

dict1 = {x: x**2 for x in range(5)}

Finalement une chose intéressante avec les dictionnaires est l'unpaking illustré par l'exemple suivant:

def add(a=0, b=0):
    return a + b
d = {'a': 2, 'b': 3}
add(**d)

a) Comment définir un dictionnaire vide ?

b) Comment concaténer plusieurs dictionnaires entre eux ?

c) On considère une liste de mots:

mots = ['Abricot', 'Airelle', 'Ananas', 'Banane', 'Cassis', 'Cerise', 'Citron',\ 
'Clémentine', 'Coing', 'Datte', 'Fraise', 'Framboise', 'Grenade', 'Groseille',\ 
'Kaki', 'Kiwi', 'Litchi', 'Mandarine', 'Mangue', 'Melon', 'Mirabelle', 'Nectarine',\ 
'Orange', 'Pamplemousse', 'Papaye', 'Pêche', 'Poire', 'Pomme', 'Prune', 'Raisin']

Écrire une fonction position(mots, x, n) qui retourne la liste des mots ayant le caractère x comme n-ième lettre (en commençant à partir de zéro comme en Python).

Réponse

['Clémentine', 'Datte', 'Groseille', 'Pêche', 'Poire', 'Pomme', 'Prune']

d) En imaginant que la liste des mots soit très longue, alors à chaque évaluation de la fonction position l'ensemble des mots est parcouru, ce qui prend pas mal de temps. Pour améliorer cela, construire un dictionnaire mots_dict ayant pour clefs les tuples (x,n) et comme valeurs la liste des mots ayant le caractère x comme n-ième lettre, c'est-à-dire tel que mots_dict[x,n] retourne la même chose que position(mots, x , n) à l'ordre près. Ainsi la liste mots n'est parcourue qu'une seule fois lors de la construction du dictionnaire et ensuite l'évaluation du dictionnaire est extrêmement rapide pour n'importe quelle requête.

• «
• 0
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• »