Trier 12 000 références : complexité algorithmique ou index SQL ?

Coût du tri par insertion Le tri par insertion effectue de l'ordre de n²/2 comparaisons dans le pire cas (liste initialement triée à l'envers) et n²/4 en moyenne. Avec n = 12 000 : 12 000² / 2 = 72 000 000 de comparaisons, en pratique un peu moins en moyenne, d'où un ordre de grandeur de 30 à 70 millions. 95 s pour ~72 millions de comparaisons donne environ 1,3 microseconde par comparaison de chaînes en PHP : le temps est bien passé dans la double boucle, pas dans le réseau ni dans MySQL.

Gain d'un tri en O(n log n) Pour un tri par fusion ou par tas : n × log₂ n = 12 000 × 13,55 ≈ 162 600 comparaisons. Rapport : 72 000 000 / 162 600 ≈ 443. Temps estimé : 95 / 443 ≈ 0,21 seconde. Le gain est d'un facteur plusieurs centaines, pas de quelques pourcents.

Projection à trois ans (+15 %/an) 12 000 × 1,15³ = 12 000 × 1,5209 ≈ 18 250 références. Tri par insertion : le coût varie comme n², donc 95 × (18 250/12 000)² = 95 × 2,31 ≈ 220 s. Dès l'année 1 : 95 × 1,15² = 125,6 s, soit déjà au-delà de max_execution_time = 120 s. La page tombera en erreur fatale avant la fin de l'exercice, sans même attendre trois ans. Avec un tri en O(n log n) : environ 0,32 s la troisième année.

Conclusion sur le serveur Un serveur plus puissant multiplierait la vitesse par 2 ou 3, alors que le changement d'algorithme la multiplie par 400. Il ne résout rien : il repousse le mur de quelques mois en dépensant du capital. La réponse est algorithmique, pas matérielle - argument à présenter avec les trois chiffres ci-dessus (95 s, 0,21 s, dépassement du plafond dès l'année 1).

Non : trier en PHP à chaque requête est une erreur de conception. Trois coûts se cumulent aujourd'hui :

1. SELECT * rapatrie 12 000 lignes (plusieurs mégaoctets) sur le réseau puis en mémoire PHP ;
2. le tri est refait intégralement à chaque affichage, alors que le contenu du catalogue ne change que quelques fois par jour ;
3. le résultat complet est probablement rendu dans une page unique, ce qui pèse aussi côté navigateur.

Correction d'architecture

• Laisser le SGBD trier et paginer :

SELECT id, code_ean, libelle, quantite
FROM article
ORDER BY libelle
LIMIT 50 OFFSET :offset;

avec un index sur libelle. Le SGBD parcourt l'index dans l'ordre demandé : plus de tri en mémoire, un coût logarithmique pour localiser le point de départ puis linéaire seulement sur les 50 lignes renvoyées.

• Paginer (25 à 50 lignes par page) et transmettre un jeu de résultats minimal : on passe de plusieurs mégaoctets à quelques kilo-octets.
• Si les filtres combinés deviennent complexes, ajouter l'index composite correspondant ((categorie, libelle)) et vérifier le plan d'exécution avec EXPLAIN : un Using filesort signale que l'index n'est pas exploité.
• Option de confort : cache applicatif ou cache HTTP de la première page, invalidé à chaque mise à jour du catalogue.

Ce qui change dans les coûts Le travail se déplace du CPU du serveur web vers le SGBD, qui est précisément l'outil conçu pour cela et qui dispose d'index et de statistiques. Le coût ne disparaît pas, il devient logarithmique et mutualisé : il ne dépend plus du nombre de consultations, mais du volume de données et du nombre de pages regardées. Gain attendu : de 95 s à quelques dizaines de millisecondes.

Point de vigilance L'ordre de tri dépend de la collation (utf8mb4_unicode_ci par exemple) : accents et majuscules ne se comparent pas comme en PHP. Il faut vérifier que l'ordre affiché correspond à l'attendu métier, et que l'index est bien créé avec la même collation que la colonne. La correction doit inclure ce contrôle, sinon on remplace une lenteur par une incohérence.

Complexité comparée

• Recherche séquentielle (code actuel) : n comparaisons au pire, n/2 en moyenne, soit 6 000 comparaisons pour 12 000 références, à chaque scan.
• Recherche dichotomique sur un tableau trié : ⌈log₂(n+1)⌉ itérations. 2¹³ = 8 192 < 12 000 ≤ 16 384 = 2¹⁴, donc 14 itérations au maximum. Rapport d'environ 430 en moyenne, 860 au pire.

Algorithme

fonction rechercherCode(tab, n, code)   // tab trié par ordre croissant sur code
    debut ← 0
    fin ← n - 1
    tant que debut ≤ fin faire
        milieu ← (debut + fin) div 2
        si tab[milieu].code = code alors
            retourner tab[milieu]
        sinon si tab[milieu].code < code alors
            debut ← milieu + 1
        sinon
            fin ← milieu - 1
        fin si
    fin tant que
    retourner null
fin fonction

Cas limites à traiter

1. Tableau vide (n = 0) : la boucle ne s'exécute pas et renvoie null ; à vérifier explicitement pour éviter un accès tab[-1].
2. Code absent : null doit produire un message « référence inconnue », pas une erreur PHP ni un ajout silencieux au stock.
3. Tableau non trié : la dichotomie renvoie un résultat faux sans erreur - le pire des cas. L'invariant « trié » doit être garanti par la source (index SQL, tri unique au chargement) et testé.
4. Doublons : si un code peut apparaître plusieurs fois (lots différents), préciser la règle (premier trouvé, ou recherche de la borne inférieure pour obtenir tous les lots).
5. Type et format : un EAN-13 commence parfois par zéro ; comparer en chaîne de 13 caractères, jamais en entier, sous peine de perdre les zéros de tête. L'ordre de comparaison doit être identique à celui du tri (même collation, même sens).
6. Validité du code : avant toute recherche, vérifier la clé de contrôle EAN-13 (somme pondérée des 12 premiers chiffres, multiple de 10) et la longueur, pour filtrer les erreurs de scan.
7. Débordement : (debut + fin) div 2 reste sûr pour 12 000 éléments ; la variante debut + (fin - debut) div 2 est une bonne habitude.

La dichotomie n'est valable que si l'on peut prouver que le tableau est trié : c'est cet invariant qui doit être testé, pas seulement l'algorithme.