Une recherche de premier cycle démontre une amélioration de la vitesse de recherche dans les tables de hachage

Introduction

• À l’automne 2021, Andrew Krapivin, étudiant de premier cycle à la Rutgers University, est tombé sur un article qui allait changer sa vie.
• Cet article portait sur de « petits pointeurs » servant à référencer des informations dans la mémoire d’un ordinateur.
• Krapivin a imaginé une méthode pour réduire la taille des pointeurs afin de diminuer la consommation mémoire.

Découverte d’une nouvelle table de hachage

• Krapivin a mené ses expériences en utilisant des tables de hachage, une méthode courante de stockage des données.
• Au cours de ses expérimentations, Krapivin a inventé un nouveau type de table de hachage fonctionnant plus rapidement que les versions existantes.
• Cette découverte a conduit à un résultat qui renverse une conjecture vieille de 40 ans en science des données.

L’importance des tables de hachage

• Les tables de hachage sont l’une des plus anciennes structures de données en informatique et offrent un stockage efficace des données.
• Elles sont conçues pour assurer trois fonctions : rechercher, supprimer et insérer des éléments.

La conjecture de Yao et sa réfutation

• En 1985, l’informaticien Andrew Yao a proposé une conjecture sur la manière de retrouver un élément dans le pire des cas dans une table de hachage possédant certaines propriétés.
• La nouvelle table de hachage de Krapivin réfute la conjecture de Yao en démontrant que le temps nécessaire, dans le pire des cas, pour les requêtes et les insertions est proportionnel à (log x)².

Nouvelle découverte sur le temps moyen de requête

• Krapivin et son équipe ont montré que, dans des tables de hachage non gloutonnes, le temps moyen de requête ne dépend pas de x.
• Cela signifie qu’il est possible d’obtenir un temps moyen de requête constant, indépendamment du taux de remplissage de la table de hachage.

Conclusion

• Cette recherche approfondit notre compréhension des tables de hachage et pourrait déboucher sur des applications concrètes.
• Une telle compréhension des structures de données pourrait servir de base à de futures améliorations pratiques.

[GN⁺]

Commentaires sur Hacker News

• Krapivin a réalisé une percée sans connaître la conjecture de Yao

  • Le développeur de Balatro a créé un deck builder primé sans connaître les deck builders existants
  • La meilleure façon d’aborder un problème consiste peut-être à ignorer, voire à ne pas connaître, les tentatives similaires antérieures
  • Le monde actuel est trop interconnecté, ce qui rend facile le fait de se retrouver prisonnier de cadres de pensée antérieurs
  • Internet est formidable, mais il tend à homogénéiser le monde des idées

• Beau résultat, mais j’ai l’impression qu’on devrait parler d’une conjecture en informatique

• Je me demande si quelqu’un connaît un dépôt GitHub avec cette implémentation

• C’est impressionnant, mais le style « culte de la personnalité » de cet article me met un peu mal à l’aise

  • Je me demande s’il était nécessaire de voir plusieurs photos d’un jeune homme prenant différentes poses dans un cadre universitaire
  • On dirait qu’il faut une version façon La La Land pour glorifier les survivants du succès informatique et encourager davantage de participation

• Dans cette nouvelle table de hachage, le temps requis dans le pire des cas pour les requêtes et les insertions est proportionnel à (log x)²

  • Le résultat de l’équipe ne débouchera peut-être pas sur des applications immédiates
  • Je ne comprends pas pourquoi cela ne déboucherait pas sur des applications immédiates
  • Je me demande si l’analyse des cas d’usage réels est une situation où une approche plus empirique permet de mieux ajuster les implémentations de hachage qu’une approche purement mathématique

• Lire cet article, c’est comme lire l’explication du problème de Monty Hall

  • La conclusion semble aller à l’encontre du bon sens, mais elle peut être démontrée
  • Le fait qu’on puisse obtenir un temps moyen de requête constant indépendamment du taux de remplissage de la table de hachage n’était même pas attendu par les auteurs

• C’est un bon test récent

  • Voyons si la deep research peut produire ce résultat sans le copier
  • gpt4, Gemini 2 et Claude n’ont pas eu de chance
  • L’informatique menée par les humains est toujours en sécurité

• Je me demande si quelqu’un a une implémentation simple de « Tiny pointers »

  • Mon esprit va d’abord vers le code / pseudo-code, avant les preuves

• Comme le disait toujours le méchant dans <i>Scooby Doo</i> :

  • <i>« Et si ce n’étaient pas ces sales gosses, j’aurais réussi ! »</i>

• En parcourant rapidement l’article, il semble que la principale différence qu’ils utilisent est que l’algorithme d’insertion de la table de hachage explore plus loin au lieu de remplir avidement le premier emplacement vide

  • Cela combine un ordre d’exploration démontrablement efficace pour trouver des emplacements vides, même lorsque la table est très remplie
  • Les insertions deviennent plus lentes quand la table est moins remplie, mais cela permet d’éviter le pire scénario où l’on ne parvient pas à trouver les derniers emplacements vides restants

• Résultat théorique intéressant, mais en pratique, l’« astuce » actuelle consistant à allouer une table plus grande que nécessaire semble être une meilleure solution

  • Par exemple, le hashbrown de Rust laisse 1/8 de la table (12,5 %) vide, utilise un peu plus de mémoire, mais permet des insertions/recherches très rapides