Structures de données

a) [2, 3, 4]              b) [0, 1, 2, 3]
c) [6, 7, 8, 9]           d) [0, 3, 6, 9]
e) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
f) [7, 8, 9]              g) []      (debut apres la fin, pas negatif)
h) []                     (pas negatif mais debut < fin)
i) [9, 8, 7]              j) []      (aucune erreur !)
k) 0                      l) [0, 1, 2, ..., 8]

a) a = [1, 2, 3]        b = [1, 2, 3]     (meme objet)
b) a = [1, 2]           b = [1, 2, 3]
c) a = [[1, 9], [2]]    b = [[1, 9], [2]]  (sous-listes partagees)
d) a = [[1], [2]]       b = [[1, 9], [2]]  (copie profonde a la main)
e) a = [[7, 0], [7, 0]]                    (la ligne est repetee par reference)
f) a = (1, [2, 3])                         (le tuple est immuable, sa liste ne l'est pas)

Le cas (f) merite un commentaire : un tuple garantit que ses references ne changent pas, pas que les objets references soient immuables. Un tel tuple n'est d'ailleurs pas hachable : hash((1, [2])) leve TypeError.

def doublons(t):
    """t contient-elle une valeur repetee ? Theta(n) en moyenne."""
    return len(set(t)) != len(t)

def doublons_precoce(t):
    """Variante s'arretant des le premier doublon trouve."""
    vus = set()
    for x in t:
        if x in vus:          # Theta(1)
            return True
        vus.add(x)
    return False

def communs(t, u):
    """Valeurs communes, triees, sans repetition."""
    return sorted(set(t) & set(u))

def uniques_en_ordre(t):
    """Elements de t sans doublon, dans l'ordre de premiere apparition."""
    vus, res = set(), []
    for x in t:
        if x not in vus:
            vus.add(x)
            res.append(x)
    return res

def anagrammes(m1, m2):
    """Les deux mots ont-ils les memes lettres avec les memes multiplicites ?"""
    return sorted(m1.lower()) == sorted(m2.lower())

assert doublons([1, 2, 3, 2])
assert not doublons([1, 2, 3])
assert communs([1, 2, 3, 3], [3, 4, 2]) == [2, 3]
assert uniques_en_ordre([3, 1, 3, 2, 1]) == [3, 1, 2]
assert anagrammes("chien", "niche")

Complexites. doublons construit un ensemble : \(\Theta(n)\) en moyenne. La version naive a deux boucles imbriquees serait en \(\Theta(n^2)\) — pour \(n = 10^5\), c'est la difference entre 0,01 s et plusieurs minutes. uniques_en_ordre utilise deux structures a la fois : l'ensemble pour la rapidite du test, la liste pour conserver l'ordre. C'est un motif tres frequent.

anagrammes coute \(\Theta(n\log n)\) a cause des tris ; une version en \(\Theta(n)\) compte les lettres dans deux dictionnaires et les compare.

notes = [("Amine", 15), ("Sara", 18), ("Youssef", 12),
         ("Amine", 11), ("Sara", 16), ("Youssef", 14)]

# 1. regroupement
par_nom = {}
for nom, note in notes:
    if nom not in par_nom:
        par_nom[nom] = []
    par_nom[nom].append(note)
# equivalent plus court :
# par_nom.setdefault(nom, []).append(note)

# 2. moyennes
moyennes = {nom: sum(v) / len(v) for nom, v in par_nom.items()}
print(moyennes)      # {'Amine': 13.0, 'Sara': 17.0, 'Youssef': 13.0}

# 3. classement : moyenne decroissante, puis nom croissant a egalite
classement = sorted(moyennes.items(), key=lambda c: (-c[1], c[0]))
for rang, (nom, m) in enumerate(classement, 1):
    print(f"{rang}. {nom:<10} {m:.2f}")

# 4. meilleure note individuelle (il peut y avoir des ex aequo)
meilleure = max(note for _, note in notes)
gagnants = [nom for nom, note in notes if note == meilleure]
print(meilleure, gagnants)      # 18 ['Sara']

1. Sara       17.00
2. Amine      13.00
3. Youssef    13.00

La cle de tri (-c[1], c[0]) realise un tri lexicographique : on compare d'abord l'oppose de la moyenne (donc decroissant), et a egalite le nom (croissant). Ce tri « a plusieurs criteres » est une technique a maitriser.

import time

def chrono(action, repetitions=1000):
    """Temps moyen d'une action, en microsecondes."""
    t0 = time.perf_counter()
    for _ in range(repetitions):
        action()
    return (time.perf_counter() - t0) / repetitions * 1e6

print(f"{'n':>8} {'liste (us)':>12} {'ensemble (us)':>14} {'rapport':>9}")
for n in (10**3, 10**4, 10**5):
    L = list(range(n))
    S = set(L)
    tl = chrono(lambda: (-1) in L, 200)
    ts = chrono(lambda: (-1) in S, 200)
    print(f"{n:>8} {tl:>12.2f} {ts:>14.4f} {tl/ts:>9.0f}")

       n   liste (us)  ensemble (us)   rapport
    1000         4.10         0.0400       102
   10000        41.30         0.0400      1033
  100000       412.00         0.0410     10049

Le temps de la liste est multiplie par 10 quand \(n\) l'est : c'est bien un comportement lineaire. Celui de l'ensemble ne bouge pas : constant.

for n in (10**4, 10**5):
    t = list(range(n))
    print(n, "append :", f"{chrono(lambda: t.append(0), 10000):.3f} us")
    u = list(range(n))
    print(n, "insert(0):", f"{chrono(lambda: u.insert(0, 0), 300):.3f} us")

3. Une liste Python est un tableau dynamique : les elements occupent des cases contigues. append ecrit dans la case libre suivante, en \(\Theta(1)\) amorti (avec de temps en temps un reagrandissement du tableau, dont le cout est reparti sur les appels precedents). insert(0, x) doit en revanche decaler les \(n\) elements d'une case vers la droite : \(\Theta(n)\). Pour des insertions en tete frequentes, on utilise collections.deque, qui les realise en \(\Theta(1)\).

def creuse(m):
    """Matrice pleine (liste de listes) -> dictionnaire {(i,j): valeur}."""
    return {(i, j): m[i][j]
            for i in range(len(m))
            for j in range(len(m[0]))
            if m[i][j] != 0}

def pleine(d, n, p):
    """Dictionnaire creux -> matrice pleine n x p."""
    m = [[0] * p for _ in range(n)]
    for (i, j), v in d.items():
        m[i][j] = v
    return m

def somme_creuse(d1, d2):
    """Somme de deux matrices creuses."""
    r = dict(d1)
    for cle, v in d2.items():
        r[cle] = r.get(cle, 0) + v
        if r[cle] == 0:
            del r[cle]          # on ne stocke jamais un zero
    return r

def produit_vecteur(d, x, n):
    """Produit d'une matrice creuse n x p par le vecteur x."""
    y = [0] * n
    for (i, j), v in d.items():
        y[i] += v * x[j]        # une seule multiplication par coefficient non nul
    return y

m = [[1, 0, 0], [0, 0, 2], [3, 0, 0]]
d = creuse(m)
assert d == {(0, 0): 1, (1, 2): 2, (2, 0): 3}
assert pleine(d, 3, 3) == m
assert produit_vecteur(d, [1, 1, 1], 3) == [1, 2, 3]

4. Pour \(n = 1000\) avec 1 % de coefficients non nuls :

import random, time
n, densite = 1000, 0.01
d = {(random.randrange(n), random.randrange(n)): random.random()
     for _ in range(int(n*n*densite))}
x = [1.0] * n

t0 = time.perf_counter(); produit_vecteur(d, x, n)
print("creuse :", time.perf_counter() - t0, "s")     # ~0.005 s

M = pleine(d, n, n)
t0 = time.perf_counter()
y = [sum(M[i][j]*x[j] for j in range(n)) for i in range(n)]
print("pleine :", time.perf_counter() - t0, "s")     # ~0.4 s

1-2. Comparaison.

La liste triee n'est interessante que si les recherches dominent largement les modifications, ou si l'on a besoin de parcourir les elements dans l'ordre — ce que la table de hachage ne permet pas.

3. Une table de hachage est un tableau de \(m\) alveoles. Une fonction de hachage \(h\) envoie chaque cle sur un indice de \(0\) a \(m-1\). Deux cles distinctes peuvent tomber dans la meme alveole (collision) : on stocke alors dans chaque alveole la liste des elements qui s'y trouvent.

class EnsembleHache:
    """Ensemble implemente par table de hachage a chainage separe."""

    def __init__(self, m=16):
        self.m = m                       # nombre d'alveoles
        self.n = 0                       # nombre d'elements
        self.table = [[] for _ in range(m)]

    def _indice(self, x):
        return hash(x) % self.m

    def contient(self, x):
        return x in self.table[self._indice(x)]

    def ajouter(self, x):
        alveole = self.table[self._indice(x)]
        if x not in alveole:
            alveole.append(x)
            self.n += 1
            if self.n > 2 * self.m:      # facteur de charge > 2 : on agrandit
                self._agrandir()

    def supprimer(self, x):
        alveole = self.table[self._indice(x)]
        if x in alveole:
            alveole.remove(x)
            self.n -= 1

    def _agrandir(self):
        """Double le nombre d'alveoles et rehache tout."""
        anciens = [x for alveole in self.table for x in alveole]
        self.m *= 2
        self.table = [[] for _ in range(self.m)]
        for x in anciens:
            self.table[self._indice(x)].append(x)

    def __len__(self):
        return self.n

E = EnsembleHache()
for k in range(1000):
    E.ajouter(k % 400)               # avec doublons
assert len(E) == 400
assert E.contient(399) and not E.contient(400)
E.supprimer(399)
assert not E.contient(399) and len(E) == 399
print("table de hachage validee")

4. Analyse. Notons \(m\) le nombre d'alveoles, \(n\) le nombre d'elements et \(\alpha = n/m\) le facteur de charge. Sous l'hypothese de hachage uniforme simple (chaque cle a la meme probabilite \(1/m\) de tomber dans chaque alveole, independamment des autres), la longueur \(L_i\) de l'alveole \(i\) suit une loi binomiale \(\mathcal{B}(n, 1/m)\), d'esperance \(\mathbb{E}[L_i] = n/m = \alpha\).

Une recherche infructueuse parcourt entierement l'alveole visee : son cout moyen est \(\Theta(1 + \alpha)\), le \(1\) representant le calcul du hachage et l'acces au tableau.

Pour une recherche fructueuse, l'element cherche est l'un des \(n\) presents ; on montre de meme que le nombre moyen de comparaisons vaut \(1 + \frac{\alpha}{2} - \frac{\alpha}{2n}\), soit encore \(\Theta(1+\alpha)\).

En maintenant \(\alpha\) borne (ici \(\alpha \le 2\) grace au doublement), le cout moyen devient \(\Theta(1)\). Le redimensionnement coute \(\Theta(n)\) mais n'intervient que tous les \(n/2\) ajouts : son cout amorti est \(\Theta(1)\) par ajout.