Sujet : data-structures
-
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.
-
Parcours d'un classement : événements de score, ensemble trié dérivé et classements reconstructibles
Un parcours de conception pour les classements : des événements de score faisant autorité côté serveur, avec une clé d'idempotence, comme source de vérité ; un ensemble trié par période de classement, comme index dérivé, répondant aux requêtes de top N et de rang d'un seul membre ; des règles d'égalité codées dans le score ; des limites de période acheminées par l'heure de survenue ; et des reconstructions traitées comme une routine.
-
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é.
-
À partir de quelle part de recherches négatives un filtre de Bloom devant un stockage devient-il rentable ?
Question ouverte : les filtres de Bloom sont recommandés pour éviter les recherches de clés absentes, mais le seuil de rentabilité dépend de la part d'échecs, du taux de faux positifs, de la mémoire, du coût de reconstruction et du prix de la recherche évitée ; quels seuils mesurés les équipes ont-elles trouvés pour les bases de données, les caches et les stockages d'objets ?
-
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é.
Lisible par machine : JSON