Structures de données

1Types abstraits et panorama des structures

Jusqu'ici, une variable contenait une seule valeur. Des qu'il s'agit de manipuler des collections — les notes d'une classe, les sommets d'un graphe, les pixels d'une image — il faut des structures de donnees. Le choix de la structure determine directement l'efficacite des algorithmes qui l'utilisent : c'est souvent la decision la plus importante d'un programme.

Les quatre criteres de classification

Panorama des structures Python

t = [3, 1, 4, 1, 5]              # list  : ordonnee, mutable, doublons
u = (3, 1, 4)                    # tuple : ordonnee, IMMUABLE, doublons
s = "MPSI"                       # str   : ordonnee, immuable, caracteres
e = {3, 1, 4, 1, 5}              # set   : NON ordonne, mutable, sans doublon -> {1,3,4,5}
d = {"a": 1, "b": 2}             # dict  : association cle -> valeur

{(1, 2), (3, 4)}         # OK : les tuples sont hachables
{[1, 2]}                 # TypeError: unhashable type: 'list'
d = {(0, 0): "origine"}  # une cle peut etre un tuple (utile pour une grille)

Operations communes aux sequences

Indexation et tranches

t = [10, 20, 30, 40, 50]
#     0    1    2    3    4      indices positifs
#    -5   -4   -3   -2   -1      indices negatifs

t[0]        # 10   premier
t[-1]       # 50   dernier (idiome a connaitre)
t[1:4]      # [20, 30, 40]   de 1 inclus a 4 EXCLU
t[:3]       # [10, 20, 30]   depuis le debut
t[2:]       # [30, 40, 50]   jusqu'a la fin
t[::2]      # [10, 30, 50]   un sur deux
t[::-1]     # [50, 40, 30, 20, 10]   renversee (copie)
t[:]        # copie superficielle complete

2Cout des operations et choix d'une structure

Le choix d'une structure se fait sur le cout des operations qu'on va effectuer le plus souvent. Voici les couts a connaitre par coeur : ils justifient toutes les decisions de conception du reste du programme.

import time

n = 200000
liste = list(range(n))
ensemble = set(liste)

t0 = time.perf_counter()
for k in range(2000):
    k in liste           # Theta(n) a chaque fois
t1 = time.perf_counter()
for k in range(2000):
    k in ensemble        # Theta(1) a chaque fois
t2 = time.perf_counter()

print(f"liste    : {t1-t0:.3f} s")     # ~ 2 s
print(f"ensemble : {t2-t1:.6f} s")     # ~ 0.0004 s

Copie superficielle et copie profonde

a = [1, 2, 3]
b = a              # PAS une copie : deux noms pour le MEME objet
b.append(4)
print(a)           # [1, 2, 3, 4]  : a a change !

c = a[:]           # copie superficielle (ou list(a), ou a.copy())
c.append(5)
print(a)           # [1, 2, 3, 4]  : a est protegee

m = [[0, 0], [0, 0]]
n = m[:]              # copie SUPERFICIELLE
n[0][0] = 9
print(m)              # [[9, 0], [0, 0]]  : les sous-listes sont PARTAGEES

import copy
n = copy.deepcopy(m)      # tout est duplique, recursivement
# ou, pour une matrice, l'idiome explicite :
n = [ligne[:] for ligne in m]

m = [[0] * 3] * 2         # PIEGE
m[0][0] = 9
print(m)                  # [[9, 0, 0], [9, 0, 0]]  : une seule ligne, dupliquee !

m = [[0] * 3 for _ in range(2)]    # CORRECT : deux listes distinctes
m[0][0] = 9
print(m)                  # [[9, 0, 0], [0, 0, 0]]

Structures lineaires classiques

Ces structures sont detaillees au chapitre 10. Retenir des maintenant que pile et file ne different que par l'ordre de sortie, et que ce simple choix change completement l'algorithme de parcours qui les utilise.

3Construire, copier, comparer

Construire une structure : les comprehensions

carres  = [k*k for k in range(6)]                   # [0, 1, 4, 9, 16, 25]
pairs   = [k for k in range(20) if k % 2 == 0]      # filtrage
couples = [(i, j) for i in range(3) for j in range(2)]   # produit cartesien
ens     = {k % 5 for k in range(20)}                # comprehension d'ensemble
dic     = {k: k*k for k in range(5)}                # comprehension de dictionnaire

Une comprehension se lit « l'expression, pour chaque element, tel que condition ». Elle remplace avantageusement une boucle avec append, mais on ne l'utilise que si elle tient lisiblement sur une ligne ou deux.

# les deux fragments sont equivalents
t = []
for k in range(6):
    if k % 2 == 0:
        t.append(k*k)

t = [k*k for k in range(6) if k % 2 == 0]

Deballage et parcours simultane

a, b, c = [1, 2, 3]                 # deballage
premier, *reste = [1, 2, 3, 4]      # premier = 1, reste = [2, 3, 4]

noms  = ["Amine", "Sara", "Youssef"]
notes = [15, 18, 12]
for nom, note in zip(noms, notes):
    print(f"{nom} : {note}")

for i, nom in enumerate(noms, start=1):
    print(i, nom)

Etude de cas — analyse d'un texte

Le meme probleme, resolu avec trois structures differentes, illustre l'impact du choix.

texte = "le chat dort le chien dort le chat mange"
mots = texte.split()

# 1. Combien de mots distincts ? -> un ensemble
distincts = set(mots)
print(len(distincts))                 # 6

# 2. Combien de fois chaque mot ? -> un dictionnaire
freq = {}
for m in mots:
    freq[m] = freq.get(m, 0) + 1
print(freq)      # {'le': 3, 'chat': 2, 'dort': 2, 'chien': 1, 'mange': 1}

# 3. Les mots par frequence decroissante ? -> une liste triee de couples
classement = sorted(freq.items(), key=lambda c: (-c[1], c[0]))
print(classement[:3])       # [('le', 3), ('chat', 2), ('dort', 2)]

Chaque question appelle sa structure : ensemble pour l'unicite, dictionnaire pour l'association, liste pour l'ordre. Vouloir tout faire avec des listes conduirait a un code quadratique et illisible.