CHAPITRE 10 : OPTIMISER SANS SE TROMPER DE COMBAT

La complexité n'est pas un exercice scolaire : c'est un outil de décision. Ce dernier chapitre dit comment s'en servir, et quand ne pas s'en servir.

Le réflexe : combien d'éléments ?

Avant d'ouvrir le code, posez la question de la taille. Elle dicte à elle seule la famille de complexité acceptable.

Ce tableau se lit dans les deux sens. Si vous devez traiter dix millions d'enregistrements, vous savez d'emblée qu'aucune double boucle n'est permise. Et si n ne dépasse jamais 20, inutile de chercher une solution élégante : la force brute suffira.

Reconnaître la vraie cause

Quand un programme est lent, deux causes très différentes, et un seul symptôme.

Le test qui tranche tient en une minute : mesurez sur n, puis sur 2n. Si le temps double, votre algorithme est bon et c'est l'implémentation qu'il faut soigner. S'il quadruple, aucune micro-optimisation ne vous sauvera.

Changer de structure, souvent, suffit

La plupart des gains spectaculaires ne viennent pas d'un algorithme astucieux mais du bon choix de structure de données.

Les trois réflexes qui règlent le plus de problèmes :

• on cherche souvent une valeur → ensemble ou dictionnaire ;
• on redemande le minimum → file à priorité ;
• on retire toujours en tête → collections.deque, où popleft() est O(1) contre O(n) pour liste.pop(0).

Un exemple complet

Problème : parmi n entiers, trouver deux valeurs dont la somme vaut une cible.

# version 1 : toutes les paires : O(n²)
def paire_v1(tab, cible):
    for i in range(len(tab)):
        for j in range(i + 1, len(tab)):
            if tab[i] + tab[j] == cible:
                return (i, j)
    return None

# version 2 : trier puis deux index : O(n log n), espace O(1)
def paire_v2(tab, cible):
    t = sorted(tab)
    g, d = 0, len(t) - 1
    while g < d:
        s = t[g] + t[d]
        if s == cible: return (t[g], t[d])
        if s < cible:  g += 1
        else:          d -= 1
    return None

# version 3 : un dictionnaire : O(n), espace O(n)
def paire_v3(tab, cible):
    vus = {}
    for i, x in enumerate(tab):
        if cible - x in vus:        # O(1)
            return (vus[cible - x], i)
        vus[x] = i
    return None

Sur un million d'entiers : la version 1 demande 5 × 10¹¹ comparaisons, soit plusieurs jours. La version 3 fait une passe, et répond en une fraction de seconde. Même problème, même langage, trois idées différentes.

Remarquez que la version 3 n'est pas gratuitement meilleure : elle réclame O(n) de mémoire, là où la version 2 travaille en espace constant. C'est encore l'échange du chapitre 9.

Ce que la complexité ne dit pas

Pour finir, les limites de l'outil : les connaître évite de le mal employer.

• Les constantes. Deux algorithmes en n log n peuvent différer d'un facteur 5.
• La mémoire cache. Un parcours de tableau contigu est plusieurs fois plus rapide qu'un parcours de liste chaînée, à complexité identique, parce que le processeur lit la mémoire par blocs.
• Les entrées-sorties. Un accès disque coûte des dizaines de milliers de fois une opération en mémoire. Notre modèle fait semblant que tout coûte pareil.
• Les petites données. Sous quelques dizaines d'éléments, la complexité ne décide de rien.
• Le parallélisme. Un O(n²) réparti sur mille cœurs peut battre un O(n log n) séquentiel.

La complexité reste pourtant le premier outil à sortir, parce qu'elle est la seule qui prédise ce qui arrivera quand les données grossiront. Les autres considérations n'interviennent qu'ensuite : une fois qu'on a écarté les algorithmes qui ne tiendront jamais la charge.

50 000 x 100 000 = 5 milliards de comparaisons par jour

index = {a.reference: a for a in catalogue}   # une fois, 200 000 operations
...
article = index.get(reference)                # O(1) par requete

vus = set()        # au lieu d'une liste
morceaux = []      # on accumule, on assemble a la fin
for ligne in lignes:
    cle = ligne.split(";")[0]
    if cle not in vus:      # O(1) maintenant
        vus.add(cle)
        morceaux.append(ligne)
resultat = "\n".join(morceaux)   # une seule allocation

# O(n) au total