Notre page d'accueil vidéo affiche désormais un nouvel ensemble de 24 recommandations à chaque actualisation, grâce au passage à l'échantillonnage par réservoir pondéré (A-Res). Ce changement a éliminé le problème de la « grille identique pour toujours » qui affectait notre flux précédent trié par score.

Pourquoi l'ancienne approche nuisait à l'expérience

Toutes les deux heures, nous récupérons les dernières vidéos tendance de huit régions et injectons les résultats dans une table SQLite. La solution naïve consistait à trier l'ensemble complet — par score de pertinence — et à prendre les 24 premiers. Cette méthode garantit l'apparition des éléments ayant les scores les plus élevés, mais elle garantit également qu'ils y restent. Une seule vidéo virale peut dominer la position 1 pendant des jours, et les utilisateurs voient une grille identique à chaque rechargement.

Au-delà de l'expérience figée, le tri de toute la table pour chaque requête oblige SQLite à charger une structure temporaire volumineuse en mémoire, ce qui est inefficace.

Ce que l'échantillonnage par réservoir pondéré nous apporte

L'échantillonnage par réservoir pondéré résout deux problèmes à la fois :

  1. Fraîcheur avec biais – la probabilité de sélection de chaque vidéo est proportionnelle à son poids (par exemple, le score de pertinence). Une vidéo ayant un poids double a deux fois plus de chances d'apparaître, mais aucun élément n'a de place garantie.
  2. Efficacité mémoire – l'algorithme ne conserve qu'un « réservoir » de taille fixe de k éléments (k = 24 pour notre flux). Il traite le flux en un seul passage, la mémoire reste donc en O(k), quel que soit le nombre de candidats reçus.

L'idée centrale est simple. Au fur et à mesure que nous parcourons les lignes entrantes, nous attribuons à chaque élément une clé aléatoire qui intègre son poids, puis nous conservons les k éléments ayant les clés les plus élevées.

L'algorithme en pratique

Pour chaque vidéo, nous :

  1. Tirons un nombre aléatoire uniforme u ∈ (0, 1).
  2. Calculons une clé k = u^(1/weight).
    (Plus le poids est élevé, plus la clé attendue est grande.)
  3. Insérons l'élément dans un min-heap (tas minimal) qui stocke les k clés les plus élevées actuelles.
    Si le tas dépasse la taille k, nous rejetons la plus petite clé.

Lorsque le flux se termine, le tas contient les 24 vidéos que nous afficherons.

Gérer les limites des nombres à virgule flottante

Lorsque le poids d'une vidéo est très élevé, u^(1/weight) converge vers une valeur indiscernable de 1,0 en arithmétique à double précision, ce qui fait que de nombreux éléments importants partagent la même clé et perdent leur caractère aléatoire. La solution consiste à travailler dans l'espace logarithmique :

  • Calculer log_key = log(u) / weight au lieu de l'expression de puissance.

Comme les logarithmes transforment l'exponentiation en multiplication, l'ordre des clés est préservé tout en évitant la chute de précision. Le calcul ne coûte pratiquement rien de plus.

Liste de contrôle pour l'implémentation

  • Structure de données : un min-heap (file de priorité) de taille k conserve efficacement les clés les plus grandes (O(log k) par insertion).
  • Type numérique : utilisez des nombres à virgule flottante de 64 bits pour u et les clés basées sur le logarithme ; ils offrent une précision suffisante pour les plages de poids typiques.
  • Vérification statistique : effectuez un test rapide de Monte-Carlo sur un petit échantillon. Si les éléments de poids 10 apparaissent environ dix fois plus souvent que ceux de poids 1, l'implémentation est correcte.
  • Streaming en un seul passage : l'algorithme n'a pas besoin de connaître le nombre total de candidats à l'avance, ce qui s'adapte naturellement à notre curseur SQLite qui fournit les lignes une par une.

À retenir

L'échantillonnage par réservoir pondéré permet à un service de recommandation vidéo de garder sa page d'accueil fraîche, de respecter les scores de pertinence et de rester léger en mémoire — le tout en un seul passage sur des dizaines de milliers de candidats. En déplaçant le calcul de la clé dans l'espace logarithmique et en utilisant un min-heap, la méthode reste à la fois précise et performante.