Un nouvel algorithme de tri de livres aux performances presque parfaites
(quantamagazine.org)- Le problème du tri de bibliothèque ne concerne pas seulement le rangement des étagères : il détermine aussi le coût du stockage séquentiel sur les disques durs et dans les bases de données, et une nouvelle étude abaisse le temps moyen d’insertion à un niveau très proche de la limite théorique
- En 1981, un algorithme déterministe et lisse (smooth) garantissait un temps moyen d’insertion de ((log n)^2), mais aucune meilleure borne supérieure n’a été trouvée pendant plus de 40 ans
- Des travaux ultérieurs sur les bornes inférieures ont montré que le meilleur possible pour les algorithmes généraux est (log n), tandis que la limite des algorithmes lisses et des algorithmes déterministes est ((log n)^2), rendant nécessaire une approche aléatoire et non lisse
- En 2022, Bender, Kuszmaul et d’autres ont abaissé la borne supérieure à ((log n)^{1.5}) avec un algorithme aléatoire à indépendance vis-à-vis de l’historique (history independent), et les travaux les plus récents atteignent ((log n)(log log n)^3) en exploitant jusqu’à une quantité limitée d’informations sur le passé
- L’écart restant se situe dans le terme (log log n), et cette avancée pourrait accélérer des applications comme le stockage et le traitement de graphes dynamiques fondés sur le list labeling
Ce que pose le problème du tri de bibliothèque
- Le problème du tri de bibliothèque consiste à minimiser le temps de déplacement nécessaire pour insérer un nouvel élément tout en conservant l’ordre trié
- Si les livres sont tassés d’un seul côté, l’ajout d’un nouveau livre au milieu oblige à en déplacer beaucoup
- Ajouter un livre d’Isabel Allende peut nécessiter de déplacer toute la collection
- Puis, ajouter un livre de Douglas Adams peut obliger à recommencer la même opération
- Répartir convenablement les espaces vides sur toute l’étagère permet de réduire le coût des insertions, mais la question clé est de savoir où laisser de la place et en quelle quantité
- Plus formellement, on parle du problème de list labeling, introduit dans un article de 1981
- Son champ d’application dépasse largement les bibliothèques et s’étend à la disposition de fichiers ou d’éléments sur les disques durs et dans les bases de données
- Le nombre d’éléments peut atteindre plusieurs milliards
- Une disposition inefficace entraîne de longs temps d’attente et un coût de calcul élevé
Les performances vues par les bornes supérieures et inférieures
- La performance d’un agencement trié est généralement évaluée par le temps nécessaire pour insérer un nouvel élément
- S’il y a (n) éléments et qu’il faut déplacer tous les livres, le temps d’insertion est proportionnel à (n)
- Cela peut être vu comme une borne supérieure du temps nécessaire pour ajouter un nouvel élément
- L’article de 1981 demandait s’il était possible de réduire fortement le temps moyen d’insertion en dessous de (n), et proposait un algorithme garantissant ((log n)^2)
- Il s’agit d’un algorithme déterministe qui ne dépend pas du hasard
- Il possède la propriété lisse (smooth), selon laquelle les éléments doivent rester répartis uniformément dans l’intervalle où se produisent les insertions ou suppressions
- Les chercheurs cherchent à resserrer l’écart entre borne supérieure et borne inférieure, et considèrent qu’un algorithme est optimal quand les deux coïncident
Les contraintes imposées par les résultats antérieurs sur les bornes inférieures
- Une étude de 2004 a montré une borne inférieure ultime : dans la version la plus générale du problème du tri de bibliothèque, aucun algorithme ne peut faire mieux que (log n)
- En 1990, on a établi que la borne inférieure pour les algorithmes lisses est ((log n)^2)
- En 2012, un résultat a montré que les algorithmes déterministes qui n’utilisent pas d’aléa ont eux aussi la même borne inférieure ((log n)^2)
- Ces résultats signifient qu’il est difficile d’améliorer la borne supérieure de 1981, ((log n)^2), avec des algorithmes uniquement lisses ou déterministes
- Michael Bender en a conclu qu’il fallait des algorithmes aléatoires et non lisses pour obtenir de meilleurs résultats
- Une méthode non lisse, qui ne répartit pas uniformément les éléments, paraissait intuitivement risquée
- Et il n’était pas évident de comprendre pourquoi des choix aléatoires aideraient
2022 : une borne supérieure abaissée grâce à l’indépendance vis-à-vis de l’historique
- En 2022, Bender, William Kuszmaul et quatre autres chercheurs ont conçu un algorithme non lisse, aléatoire et à indépendance vis-à-vis de l’historique
- Un algorithme à indépendance vis-à-vis de l’historique ne révèle pas les états passés de l’étagère
- Kuszmaul a donné l’exemple d’une personne retirant un livre d’une étagère sans qu’une autre puisse s’en apercevoir
- Cette propriété peut être utile pour des raisons de confidentialité ou de sécurité
- Cet algorithme a été le premier à améliorer la borne supérieure de 1981, en ramenant le temps moyen d’insertion à ((log n)^{1.5})
- Kuszmaul a été surpris de voir qu’un outil généralement utilisé pour la confidentialité pouvait aussi rendre un algorithme plus rapide
- Helen Xu, du Georgia Institute of Technology, estime que l’idée d’utiliser l’indépendance vis-à-vis de l’historique pour autre chose que la sécurité pourrait influencer d’autres problèmes
Travaux les plus récents : combiner information historique limitée et aléa
- Dans leur article le plus récent, Bender, Kuszmaul et leurs collègues ont encore abaissé la borne supérieure pour atteindre ((log n)(log log n)^3)
- Cette valeur correspond à ((log n)^{1.000…1}), donc très proche de la borne inférieure ultime (log n)
- La nouvelle approche est elle aussi non lisse et aléatoire, mais elle utilise cette fois une dépendance limitée à l’historique (history dependence)
- L’algorithme observe en partie les tendances passées pour se préparer aux insertions futures
- Si de nombreux livres d’auteurs dont le nom commence par N, comme Nabokov, Neruda ou Ng, sont arrivés, il laisse un peu plus d’espace dans la zone N
- Mais réserver trop d’espace pourrait devenir problématique si beaucoup de livres d’auteurs commençant par A arrivent ensuite
- Bender explique que cette approche devient utile grâce à une randomisation stratégique de la quantité de passé prise en compte au moment de décider
- Seth Pettie estime que cette étude utilise l’aléa d’une manière totalement différente de l’article de 2022
L’écart restant et les applications possibles
- L’écart restant se réduit à un petit terme en (log log n)
- Bender dit ne pas encore savoir s’il faut continuer à abaisser la borne supérieure ou relever la borne inférieure
- Pettie estime que lorsque l’écart est aussi faible et qu’une borne semble naturelle tandis que l’autre paraît artificielle, c’est généralement la borne naturelle qui finit par être la bonne
- Selon lui, les améliorations futures ont plus de chances de faire descendre la borne supérieure jusqu’à (log n)
- Il ajoute toutefois que « le monde est plein de surprises étranges »
- Brian Wheatman, de l’University of Chicago, considère que ces articles représentent une amélioration théorique importante, avec aussi un fort potentiel d’amélioration en pratique
- Helen Xu explique qu’elle s’intéressait récemment à l’usage de structures de données fondées sur le list labeling pour stocker et traiter des graphes dynamiques, et que cette avancée les rendra presque certainement plus rapides
1 commentaires
Avis de Hacker News
J’ai aussi été surpris par l’idée qu’« un outil utilisé pour la protection de la vie privée puisse apporter d’autres avantages ».
En y réfléchissant, la plupart des gains de performance ne consistent pas littéralement à « exécuter plus d’instructions par heure », mais plutôt à choisir une façon de faire moins de travail.
Ici, la propriété de sécurité qu’est l’indépendance de l’historique signifie aussi qu’« il n’est pas nécessaire de suivre l’historique, et qu’on ne peut littéralement pas le faire » ; cela ressemble donc à une approche intéressante des performances, qui utilise la cryptographie comme contrainte pour empêcher du travail inutile.
Si j’ai bien compris, le modèle autorise un temps de calcul illimité.
Par exemple, si l’on sait qu’une liste est triée, on peut utiliser une recherche binaire. Mais peut-être que choisir quelle quantité d’information omettre peut aussi être central. Cela dit, on voit moins souvent ce genre de cas, et aucun exemple simple ne me vient immédiatement.
Suis-je le seul à avoir essayé de retrouver les articles clés décrits dans l’article, c’est-à-dire l’article sur le problème original et celui sur l’algorithme presque optimal [1], [2] ?
Les deux semblent être liés assez profondément dans l’article, mais ce serait très utile aux lecteurs si Quanta regroupait obligatoirement toutes les références à la fin.
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
https://link.springer.com/chapter/10.1007/3-540-10843-2_34
Dans « This problem was introduced in a 1981 paper », « 1981 paper » pointe vers https://link.springer.com/chapter/10.1007/3-540-10843-2_34, et dans le paragraphe suivant, « Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers », « a study » pointe vers https://arxiv.org/abs/2405.00807.
Les deux se trouvent dans les troisième et quatrième paragraphes de l’introduction, avant d’entrer dans les détails, l’historique et le contexte. Si cela compte comme « profondément dans l’article », alors nous n’avons clairement pas la même définition de profondément.
La semaine dernière, je regardais justement ce problème. Je voulais placer les éléments d’une table de base de données à des positions arbitraires, tout en évitant autant que possible de toucher au reste de la liste.
Par exemple, si l’utilisateur ajoute un nouvel élément après l’élément 5, ce nouvel élément devient le 6, mais les éléments qui se trouvaient déjà après le 5 ne sont pas mis à jour. Il existe réellement des algorithmes très sophistiqués pour gérer ce problème et minimiser ses limites théoriques.
Cela dit, pour cette version précise, utiliser des indices fractionnaires et payer de temps à autre le coût d’un réagencement de la liste semblait être la solution la plus simple.
En gros, il fonctionne bien quand l’espace des étiquettes est grand par rapport au nombre d’éléments. Sinon, il faut des méthodes plus sophistiquées. Par exemple, si les étiquettes ne font que 4 octets et qu’il y a un milliard d’éléments, cela devient problématique.
De mémoire, la vraie solution consistait à laisser des intervalles entre les éléments. Par exemple, utiliser 0, 100, 200 au lieu de 0, 1, 2, puis réindexer quand c’est nécessaire. Ça devrait fonctionner suffisamment bien.
Ce qui m’était venu à l’esprit, comme mentionné, c’était l’indexation fractionnaire, mais comme gérer des décimales est pénible, on peut les représenter par des vecteurs, puis représenter ces vecteurs sous forme de chaînes numériques triées lexicographiquement.
Un élément inséré entre 1 et 2 reçoit l’index 11. N’importe quelle valeur entre 11 et 19 est possible. Entre 1 et 11, ce serait 101 ; entre 11 et 2, ce serait 12, et ainsi de suite. Mais ces index ne sont pas des nombres : ce sont des chaînes comparées lexicographiquement.
Il y a sûrement des inconvénients. Par exemple, trier de tels index consommerait beaucoup plus de mémoire, puisque les chaînes sont bien plus grosses que les nombres. Cela paraît aussi trop malin pour ne pas cacher un défaut inattendu.
En pratique, cette limite est très restreinte, mais la différence devient vraiment problématique si l’on ne se contente pas d’attribuer des étiquettes d’ordre à une collection, et que l’on utilise directement ces étiquettes comme indices de tableau pour stocker les éléments. C’est ce dernier cas qui modélise plus littéralement le problème du tri en bibliothèque.
Je me souviens avoir présenté à des étudiants, il y a quelques années, un problème basé sur l’algorithme Library Sort.
Le titre de l’article original m’est resté très clairement en tête : « Insertion Sort is O(n log n) ».
Le titre fait assez clickbait.
Je me demande si cet algorithme a vraiment une raison d’être plus rapide que les méthodes actuellement utilisées en conditions réelles.
Là où j’ai surtout rencontré ce problème, c’est dans les tableaux de nœuds de B-tree ; dans ce cas, je doute que ce soit plus rapide que d’utiliser simplement
memmove(), et pour de très grands tableaux, il me semblerait plus simple d’utiliser un B-tree.Dans ce cas, cet algorithme ferait partie de ces algorithmes asymptotiquement plus rapides, mais paradoxalement plus lents que ceux utilisés en pratique. Les algorithmes rapides de multiplication de matrices, plus lents que les bonnes implémentations de l’algorithme scolaire en O(n^3) (GEMM), en sont un exemple.
Le premier exemple de la page contient une citation qui explique bien leur utilité :
« Comme exemple de galactic algorithm, la méthode connue la plus rapide pour multiplier deux nombres repose sur une transformée de Fourier en 1729 dimensions. Elle ne nécessite que O(n log n) opérations sur les bits, mais les constantes cachées dans la notation grand O sont si grandes qu’elle n’est pas utilisée en pratique. Cela montre néanmoins pourquoi de tels algorithmes peuvent être utiles. Les auteurs disent “espérer qu’avec de nouvelles améliorations, elle deviendra pratique pour des nombres de seulement des milliards, voire des billions, de chiffres”. »
L’affirmation selon laquelle
on abaisse la borne supérieure à (log n) × (log log n)^3 — ce qui correspond à (log n)^(1,000...1)est exacte.L’un des aspects élégants quand on regarde la complexité grand O dans la famille de référence des polynômes, c’est que les logarithmes donnent des infinitésimaux. De quoi répondre à ceux qui disent que « les infinitésimaux n’existent pas vraiment ».
J’ai été surpris d’apprendre comment la British Library gère des millions de livres et de très nombreuses nouveautés chaque semaine.
Le premier livre arrivé au début de l’année a été placé à l’emplacement 2025.0000001 sur l’étagère, et le suivant juste à côté en 2025.0000002. Le reste est géré par le catalogue électronique.
Il n’est pas nécessaire de remélanger les livres, mais ce n’est pas une solution adaptée à une recherche en parcourant les rayonnages.
Au contraire, ils évitent délibérément les similarités pour empêcher les préparateurs de prendre un article ressemblant mais incorrect.
Chez moi aussi, j’oublie souvent où j’ai rangé des objets que j’utilise de temps en temps. Par exemple dans quelle boîte de quel placard j’ai mis les recharges de lames de cutter X-Acto. À force de regrouper les objets similaires, une boîte déborde tandis qu’une autre est à moitié vide.
J’imagine parfois suivre tous mes biens dans une feuille de calcul pour noter dans quelle boîte ils se trouvent, afin de ne rien perdre et d’utiliser l’espace de rangement de façon optimale. Mais il est évident que j’oublierais de la mettre à jour en ajoutant de nouveaux objets, et cela ressemble à une méthode étrangement inhumaine, plutôt faite pour des robots que pour des humains.
L’animation en haut de l’article m’a donné envie d’en faire un économiseur d’écran.
J’essaie d’identifier la contrainte centrale. La définition du problème suppose-t-elle un tableau de longueur fixe préalloué ?
insert(X),delete(X),label(X)labelrécupère l’étiquette de l’élément X, qui a été inséré auparavant et n’a pas encore été supprimé. L’étiquette est un nombre de 0 à n-1, où n est le nombre d’éléments actuellement stockés.