Les Listes

1La liste : structure, operations et couts

La liste est la structure de donnees centrale de Python. Presque tous les algorithmes du programme la manipulent : il faut en connaitre le comportement exact, y compris ses pieges.

Creation

t = []                            # liste vide
t = [3, 1, 4, 1, 5]               # en extension
t = [0] * 10                      # dix zeros
t = list(range(5))                # [0, 1, 2, 3, 4]
t = list("MPSI")                  # ['M', 'P', 'S', 'I']
t = [k*k for k in range(5)]       # comprehension
t = [1, "deux", 3.0, [4]]         # heterogene : possible, mais rarement souhaitable

Acces et modification

t = [10, 20, 30, 40, 50]
t[0]           # 10
t[-1]          # 50      dernier element
t[2] = 99      # modification en place : [10, 20, 99, 40, 50]
t[1:3] = [0]   # affectation par tranche : [10, 0, 40, 50]
len(t)         # 4

Methodes qui modifient / qui renvoient

t = [3, 1, 2]
t = t.sort()      # t vaut None !  sort ne renvoie rien
t = sorted(t)     # correct si l'on veut une nouvelle liste
t.sort()          # correct si l'on veut trier sur place

Parcours et modification simultanes : danger

t = [1, 2, 2, 3, 2]
for x in t:
    if x == 2:
        t.remove(x)       # NE JAMAIS FAIRE : le parcours saute des elements
print(t)                  # [1, 3, 2]  : resultat faux

Supprimer pendant le parcours decale les indices. Trois solutions correctes :

t = [x for x in t if x != 2]        # 1. reconstruction (la plus claire)
for i in range(len(t)-1, -1, -1):   # 2. parcours a l'envers
    if t[i] == 2:
        del t[i]
t[:] = [x for x in t if x != 2]     # 3. modification en place par tranche

La forme t[:] = ... est utile quand la liste est partagee avec l'appelant : elle modifie l'objet, alors que t = ... ne ferait que rattacher le nom local.

2Algorithmes fondamentaux et tri

Les algorithmes fondamentaux sur les listes

Ces quelques fonctions sont a savoir reecrire sans hesiter : elles reviennent dans presque tous les sujets.

def somme(t):
    """Somme des elements de t."""
    s = 0
    for x in t:
        s += x
    return s

def maximum(t):
    """Plus grand element de la liste non vide t."""
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

def indice_min(t, debut=0):
    """Indice du plus petit element de t[debut:]. Precondition : debut < len(t)."""
    imin = debut
    for i in range(debut + 1, len(t)):
        if t[i] < t[imin]:
            imin = i
    return imin

def renverse(t):
    """Renverse t EN PLACE, en Theta(n) et sans memoire auxiliaire."""
    g, d = 0, len(t) - 1
    while g < d:
        t[g], t[d] = t[d], t[g]
        g += 1
        d -= 1

def occurrences(t, v):
    """Nombre d'occurrences de v dans t."""
    c = 0
    for x in t:
        if x == v:
            c += 1
    return c

def aplatir(m):
    """[[1,2],[3],[4,5]] -> [1,2,3,4,5]."""
    res = []
    for ligne in m:
        for x in ligne:
            res.append(x)
    return res

Insertion dans une liste triee

def insere_trie(t, x):
    """Insere x dans la liste t supposee triee, en preservant le tri. Theta(n)."""
    i = len(t)
    t.append(x)                 # on agrandit d'une case
    while i > 0 and t[i-1] > x:
        t[i] = t[i-1]           # decalage vers la droite
        i -= 1
    t[i] = x

t = [1, 3, 7, 9]
insere_trie(t, 5)
assert t == [1, 3, 5, 7, 9]

C'est exactement le coeur du tri par insertion (chapitre 12) : trier, c'est inserer chaque element a sa place dans la partie deja triee.

Le tri : sort et sorted

t = [3, 1, 4, 1, 5]
t.sort()                     # trie t EN PLACE, renvoie None
u = sorted(t)                # renvoie une NOUVELLE liste, t inchangee
t.sort(reverse=True)         # ordre decroissant

Le parametre key

mots = ["banane", "kiwi", "pomme", "abricot"]

sorted(mots)                          # alphabetique
sorted(mots, key=len)                 # par longueur croissante
sorted(mots, key=str.lower)           # insensible a la casse
sorted(mots, key=lambda m: m[-1])     # par derniere lettre

eleves = [("Sara", 18, 2), ("Amine", 15, 1), ("Ines", 18, 1)]
sorted(eleves, key=lambda e: (-e[1], e[0]))   # note decroissante, puis nom

key est appliquee une seule fois a chaque element (decoration), ce qui est bien plus efficace qu'une fonction de comparaison appelee \(\Theta(n\log n)\) fois.

eleves.sort(key=lambda e: e[0])        # d'abord par nom
eleves.sort(key=lambda e: -e[1])       # puis par note : les ex aequo restent
                                        # classes par nom grace a la stabilite

Comparaison de listes

[1, 2, 3] == [1, 2, 3]      # True  : element par element
[1, 2] < [1, 3]             # True  : ordre lexicographique
[1, 2] < [1, 2, 0]          # True  : un prefixe est plus petit
[2] < [1, 9, 9]             # False : on compare 2 et 1 d'abord

L'ordre lexicographique est celui du dictionnaire : on compare les premiers elements ; en cas d'egalite, on passe aux suivants ; si l'une des listes s'epuise, elle est la plus petite.

3Visualisation interactive et etudes de cas

La visualisation ci-dessous montre ce qui se passe reellement en memoire lors des operations usuelles : elle rend concret le cout des decalages.

Etude de cas — le triangle de Pascal

Les coefficients binomiaux verifient \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). Chaque ligne se deduit de la precedente.

def pascal(n):
    """Les n+1 premieres lignes du triangle de Pascal."""
    tri = [[1]]
    for i in range(1, n + 1):
        prec = tri[-1]
        ligne = [1]
        for k in range(1, i):
            ligne.append(prec[k-1] + prec[k])
        ligne.append(1)
        tri.append(ligne)
    return tri

for ligne in pascal(5):
    print(" ".join(f"{x:3}" for x in ligne).center(30))

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1

Complexite : \(\sum_{i=0}^{n} (i+1) = \Theta(n^2)\) additions, ce qui est optimal puisqu'il y a \(\Theta(n^2)\) coefficients a produire.

def ligne_pascal(n):
    """n-ieme ligne du triangle, en Theta(n) memoire."""
    ligne = [1] * (n + 1)
    for i in range(1, n + 1):
        for k in range(i - 1, 0, -1):     # PARCOURS A L'ENVERS : indispensable
            ligne[k] += ligne[k-1]
    return ligne

assert ligne_pascal(5) == [1, 5, 10, 10, 5, 1]
from math import comb
assert ligne_pascal(20) == [comb(20, k) for k in range(21)]