Sujet : algorithms
-
Ordre des dépendances par parcours de graphe : BFS, DFS et tri topologique
Modéliser les dépendances comme un graphe orienté, utiliser un parcours en largeur ou en profondeur pour trouver tout ce qu'affecte un changement, et l'algorithme de Kahn ou l'ordre post-fixe du DFS pour produire un ordre de build ou de migration qui signale les cycles au lieu de les dissimuler ; graphlib et tsort implémentent le tri.
-
Les tables de hachage en pratique : collisions, facteur de charge et hachage avec graine
Une table de hachage n'est rapide en moyenne que tant que les clés se répartissent uniformément entre les compartiments (buckets) ; les collisions, le facteur de charge qui déclenche le rehachage, et la graine de hachage propre à chaque processus contre le hash flooding déterminent son comportement réel. Ne jamais persister des valeurs de hachage ni se fier à l'ordre d'itération.
-
La programmation dynamique pas à pas : dériver la distance d'édition
La programmation dynamique transforme une définition récursive à sous-problèmes chevauchants en un algorithme polynomial : définir l'état, écrire la récurrence et les cas de base, mémoïser ou remplir une table, puis réduire la mémoire utilisée. La distance d'édition entre deux chaînes est intégralement dérivée à titre d'exemple travaillé.
-
Récursion contre itération : profondeur de pile, limites et quand convertir
La récursion reflète les problèmes en forme d'arbre mais consomme une trame de pile par niveau ; la pile est bornée par la limite de récursion de l'interpréteur ou la taille de pile du thread, si bien qu'une récursion dont la profondeur dépend de l'entrée est un plantage en puissance. Convertir vers une pile explicite ou une boucle lorsque la profondeur croît avec la taille de l'entrée.
-
Échantillonnage par réservoir : un échantillon uniforme à partir d'un flux de longueur inconnue
Conserver k éléments d'un flux sans en connaître la longueur : remplir le réservoir avec les k premiers éléments, puis remplacer un emplacement choisi au hasard avec une probabilité k/i pour l'élément i. Une seule passe, une mémoire en O(k), chaque élément se retrouve dans l'échantillon avec une probabilité exactement égale à k/n, ce que montre un court argument télescopique.
-
Les tries pour les recherches par préfixe : autocomplétion et correspondance du plus long préfixe
Un trie stocke des chaînes de caractères avec un nœud par préfixe commun, si bien que la recherche coûte la longueur de la clé, quel que soit le nombre de clés existantes ; toutes les clés partageant un préfixe forment un même sous-arbre, et le plus long préfixe stocké d'une requête se trouve en un seul parcours ; l'utiliser pour l'autocomplétion et le routage, en le comparant d'abord à un tableau trié.
-
Pièges de la recherche binaire : dépassement de capacité du point médian et bornes décalées d'une unité
La recherche binaire est courte et notoirement facile à mal implémenter : le point médian (low + high) / 2 déborde des entiers à largeur fixe, les bornes inclusives et exclusives se mélangent, et les doublons posent la question de l'indice à renvoyer. Utiliser une bibliothèque ou la forme à prédicat monotone avec des intervalles semi-ouverts, et tester les bords.
-
Raisonner sur la complexité avant d'optimiser
La complexité asymptotique prédit comment le temps d'exécution croît avec la taille de l'entrée ; repérer en relecture de code les boucles quadratiques, les recherches linéaires répétées et la récursion non bornée évite la plupart des incidents de performance avant même qu'un profilage soit nécessaire.
-
Seau à jetons, seau percé et fenêtre glissante : en quoi diffèrent les algorithmes de limitation de débit
Les fenêtres fixes sont peu coûteuses mais laissent passer le double de la limite à une frontière ; les journaux glissants sont exacts mais stockent chaque horodatage ; les compteurs à fenêtre glissante approximent en mémoire constante ; les seaux à jetons autorisent des rafales jusqu'à la taille du seau, à un taux de remplissage fixe ; les seaux percés lissent la sortie en retardant. nginx et Envoy documentent ces deux derniers.
-
Filtres de Bloom : appartenance probabiliste à un ensemble, sans faux négatifs
Un filtre de Bloom répond « certainement absent de l'ensemble » ou « probablement présent dans l'ensemble » au moyen d'un petit tableau de bits et de k fonctions de hachage ; les faux positifs sont ajustables, les faux négatifs sont impossibles, la suppression n'est pas prise en charge. Il permet d'éviter des recherches pour des clés absentes, et tout résultat positif doit toujours être vérifié auprès de la source de vérité.
-
Heuristiques A* : préserver le sens du coût de déplacement
Choisir une heuristique qui minore le coût réel du graphe de déplacement effectif, gérer correctement les trajets améliorés et vérifier la qualité du chemin par rapport à une recherche non informée.
-
Utiliser un seau à jetons (token bucket) pour les appels d'outils
Mettre en œuvre des rafales bornées avec une équation explicite de réapprovisionnement des jetons, une consommation atomique et une limite distincte sur les requêtes en cours.
-
Stabilité du tri : ce qu'elle garantit et quand elle compte
Un tri stable conserve l'ordre d'entrée des éléments considérés égaux. Python le garantit, l'ECMAScript l'exige depuis 2019, Go et GNU sort le proposent en option ; cela détermine si les tris multi-clés, les tableaux triables et les requêtes paginées se comportent de façon prévisible.
Lisible par machine : JSON