BUT Informatique: Optimiser des applications informatiques

« Optimiser des applications informatiques » évalue la capacité à raisonner sur le coût d'un algorithme et sur les ressources d'une application : temps CPU, mémoire, entrées-sorties, réseau, base de données. L'épreuve ne demande pas de micro-optimiser au hasard, mais de mesurer, de localiser le goulot d'étranglement, puis de choisir la bonne structure ou le bon mécanisme.

Règles et concepts clés

• Complexité asymptotique : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Elle décrit la croissance quand n grandit, pas le temps exact ; sur un petit n, une liste peut battre une table de hachage.
• Mesurer avant d'optimiser (Knuth) : profiler (cProfile, JFR/VisualVM, EXPLAIN ANALYZE en SQL, onglet Performance du navigateur). Une intuition fausse sur le goulot est la première cause d'optimisation inutile.
• Structures : liste pour l'itération et l'accès indexé ; HashMap/set pour la recherche en O(1) moyen ; arbre équilibré pour les parcours ordonnés en O(log n).
• Entrées-sorties et base : le motif N+1 (une requête par élément d'une boucle) coûte souvent plus cher que tout le code applicatif ; on le remplace par une jointure ou un chargement en lot. Un index B-tree accélère WHERE et JOIN mais ralentit les écritures et occupe de l'espace.
• Cache et mémoïsation : pertinents si les lectures sont répétées et la donnée peu volatile ; il faut une politique d'invalidation, sinon on sert des données périmées.
• Parallélisme : la loi d'Amdahl borne le gain (une partie séquentielle de 10 % limite le gain à ×10) ; attention aux accès concurrents, aux interblocages et au coût de création de threads (utiliser un pool).

Exemple travaillé

Détecter les doublons dans 100 000 identifiants. Version naïve : double boucle, environ n²/2 = 5·10⁹ comparaisons, plusieurs minutes. Version HashSet : n insertions, O(n) ≈ 10⁵ opérations, quelques millisecondes, au prix de ~10⁵ entrées en mémoire. Si la mémoire est contrainte, on trie (O(n log n), ~1,7·10⁶ opérations) puis on compare les voisins, sans structure auxiliaire. Le choix dépend donc des contraintes mémoire, pas seulement du temps.

Pièges qui coûtent des points

• Micro-optimiser une boucle alors que 90 % du temps se passe dans une requête SQL non indexée.
• Confondre complexité et temps mesuré : un O(n²) compilé peut battre un O(n) interprété sur de petites tailles.
• Ajouter des threads et attendre un gain linéaire.
• Indexer une colonne à deux valeurs distinctes : peu sélectif, coût d'écriture sans gain de lecture.
• Oublier la complexité mémoire du cache.