Introduction
- Un nouvel algorithme propose une méthode pour résoudre le problème du tri en bibliothèque.
- Ce problème ne s’applique pas seulement au rangement de livres, mais aussi à l’agencement de fichiers sur des disques durs et dans des bases de données.
- Cette nouvelle approche combine l’historique du contenu d’une étagère et le hasard pour produire des résultats proches de l’idéal théorique.
Réduire les bornes
- La manière la plus courante d’évaluer une étagère bien ordonnée consiste à regarder le temps nécessaire pour insérer chaque élément individuellement.
- Un article de 1981 a posé la question de savoir s’il était possible de concevoir un algorithme dont le temps moyen d’insertion soit bien inférieur à n.
- Une étude de 2004 a montré que la borne inférieure optimale du problème du tri en bibliothèque est
log n.
- Elle a également montré qu’avec des algorithmes lisses ou déterministes, il est impossible d’obtenir un temps moyen d’insertion meilleur que
(log n)².
Une histoire secrète
- En 2022, Bender et ses collègues ont essayé un algorithme aléatoire et non lisse, réduisant le temps moyen d’insertion à
(log n)¹.⁵.
- Cet algorithme ne dépend pas de l’historique passé de l’étagère, ce qui peut être utile pour des raisons de sécurité.
Réduire l’écart
- Bender et Kuszmaul ont abaissé la borne supérieure à
(log n) × (log log n)³, se rapprochant fortement de la borne inférieure théorique.
- Cet algorithme utilise un degré limité de dépendance à l’historique afin de planifier des événements futurs.
- Ce résultat s’appuie sur des travaux antérieurs tout en exploitant le hasard d’une manière totalement différente.
Conclusion
- Cette recherche représente une avancée importante sur le plan théorique et présente aussi un fort potentiel d’amélioration dans les applications.
- Le terme
log log n empêche encore une solution complète, et la réponse pourrait être soit d’abaisser la borne supérieure, soit de relever la borne inférieure.
1 commentaires
Commentaires Hacker News
Il est intéressant de voir que des techniques cryptographiques peuvent être utilisées pour améliorer les performances. La performance ne consiste pas seulement à exécuter plus d’instructions, mais à choisir comment faire moins de travail. La propriété de sécurité appelée « indépendance de l’historique » signifie qu’on n’effectue pas de travail de suivi du passé
Il est difficile de retrouver les principaux articles de recherche mentionnés dans l’article. Il serait utile aux lecteurs que Quanta liste toutes les références à la fin de l’article
Il existe des algorithmes complexes pour résoudre le problème du placement arbitraire d’éléments dans une table de base de données. Pourtant, une solution simple à ce problème consiste à utiliser des valeurs fractionnaires et à réorganiser occasionnellement la liste
Je me souviens avoir posé ce problème à des étudiants à partir de l’algorithme « Library Sort ». Le titre de l’article original est « Insertion Sort is O(n log n) »
Je me demande s’il y a une raison pour que ce soit réellement plus rapide que les algorithmes actuellement utilisés. Dans le tableau de nœuds d’un B-tree, utiliser
memmove()pourrait être plus rapide. Pour les grands tableaux, il est plus simple d’utiliser un B-treeJe me demande si l’énoncé du problème suppose un tableau préalloué de longueur fixe
Je suis surpris par la manière dont la British Library gère ses livres. Une fois qu’un livre arrive, le catalogue électronique s’occupe du reste, ce qui évite d’avoir à réorganiser les livres
J’aimerais transformer l’animation en haut de l’article en économiseur d’écran
Liens propres pour les utilisateurs mobiles
Il s’agit bien d’abaisser la borne supérieure à (log n) multiplié par (log log n)^3. Il est intéressant de voir que, dans la complexité big-O avec des classes de référence polynomiales, les logarithmes fournissent des valeurs infiniment petites