Le titre complet de l'article aurait dû être «Tri« topologique »durable d'un graphique avec des cycles en
O(|V| + |e| log |e|) dans le temps et
O(|V|) en mémoire sans récursivité», mais on m'a dit qu'est-ce que c'est exagéré.
Avertissement: je suis un programmeur, pas un mathématicien, donc un langage inexact est possible dans des endroits pour lesquels vous pouvez et devez donner un coup de pied.
Essence de la tâche
J'analyserai le libellé du problème, dont je veux partager la solution en partie.
Le tri topologique est l'ordre des sommets d'un graphe acyclique dirigé dans lequel chacun des sommets d'où sort l'arête vient plus tôt que le sommet dans lequel cette arête entre. Il y a deux nuances importantes ici: un graphique peut avoir
plusieurs ordonnances de ce type et il ne s'applique qu'aux graphiques
acycliques . Les mathématiciens s'en moquent, mais les programmeurs veulent parfois du déterminisme et un peu plus que "Je suis désolé, vous avez un cycle ici, vous n'aurez pas de tri".
Par conséquent, nous ajoutons l'exigence de
stabilité : une paire de sommets, dont l'ordre n'est pas spécifié par les bords du graphique, doit être déterminée par l'ordre dans lequel ces sommets sont arrivés à l'entrée de l'algorithme. Par conséquent, les tris répétés ne changeront pas l'ordre des sommets.
Avec l'absence de
récursivité, tout est simple, l'ordinateur est nettement plus faible que la machine de Turing et la mémoire (et surtout la pile) a limité. Par conséquent, en programmation appliquée, les algorithmes itératifs sont généralement préférables aux algorithmes récursifs.
Et enfin, je définirai ce que j'appelle le tri «topologique» s'il y a des
cycles dans le graphique. Il s'agit de l'ordre des sommets, qui coïncide avec le véritable tri topologique, si chacun des cycles est remplacé par un sommet, et les sommets du cycle lui-même, conformément à l'exigence de stabilité, sont situés les uns par rapport aux autres dans l'ordre d'origine.
Et maintenant,
avec toutes ces ordures, nous allons essayer de décoller. Je vais tout faire dans le cadre des restrictions de temps et de mémoire indiquées au début de l'article.
Rechercher une solution
Si vous regardez les algorithmes existants pour le tri topologique (
algorithme de Kahn ,
recherche approfondie ), il s'avère que tous, s'il y a un cycle, dites "je ne peux pas" et arrête de fonctionner.
Par conséquent, allons-y d'un autre côté, avec des algorithmes qui peuvent faire quelque chose d'intelligible avec des cycles. Par exemple,
trouvez- les. Parmi les
algorithmes répertoriés dans Wikipedia
pour trouver des cycles dans les graphiques , l'attention a été attirée sur
l'algorithme Taryan . Il contient une remarque intéressante selon laquelle, en tant que sous-produit, l'algorithme produit le tri topologique
inverse du graphique:
Bien qu'il n'y ait rien de spécial à propos de l'ordre des nœuds dans chaque composant fortement connecté, une propriété utile de l'algorithme est qu'aucun composant fortement connecté ne sera identifié avant aucun de ses successeurs. Par conséquent, l'ordre dans lequel les composants fortement connectés sont identifiés constitue une sorte topologique inverse du DAG formé par les composants fortement connectés .
Certes, l'algorithme est récursif et il n'est pas clair ce qu'il a avec la stabilité, mais c'est clairement un mouvement dans la bonne direction. Une lecture plus approfondie de Wikipédia révèle une référence à l'article
Un algorithme économe en espace pour trouver des composants fortement connectés , écrit par le camarade David Pierce, dans lequel non seulement il existe un algorithme impératif, mais il a également réduit les besoins en mémoire par rapport au classique Algorithme de Tarjan. Le bonus est la
mise en œuvre de l'algorithme en Java . Doit prendre!
Algorithme PEA_FIND_SCC3 (V, E) de l'article de Pierce Nous avons donc une liste de sommets en entrée et (grâce à Pierce) un certain indice de la composante de forte connectivité à laquelle appartient ce sommet en sortie. L'étape suivante consiste à trier de manière stable les sommets en fonction du numéro de série de leur composant. Il existe un algorithme pour une telle tâche, il est appelé
comptage tri , qui effectue cela en temps
O(n) .
Dans le processus de regroupement de l'algorithme en tas, il s'est avéré que le fait qu'il soit naturel de lui donner le tri topologique
inverse est en fait très extérieur à Taryan - puis les branches voisines du graphique (n'ayant pas de relation d'ordre entre elles) seront numérotées à l'envers, puis les morceaux du graphique ne seront pas ayant des connexions entre eux, se révèlent être dans l'ordre inverse ...
La réponse
Donc, la solution finale:
- Nous numérotons les sommets de la liste d'origine.
O(|V|) - Nous trions les bords de chaque sommet en fonction du numéro du sommet auquel va le bord.
O(|e| log |e|) - En utilisant l'algorithme Pierce, nous trouvons et numérotons les composants d'une connexion forte.
O(|V|) - En utilisant le tri par comptage, nous trions les sommets en fonction du nombre de composants fortement connectés qu'ils ont reçus.
O(|V|)
Code GitHub, Java, domaine public . On peut noter que pour assurer la stabilité du tri, l'algorithme de Pierce est légèrement modifié et contourne les sommets dans l'ordre inverse.
Mais pourquoi ???
Et maintenant le contexte, pourquoi tout cela était nécessaire. Lors du chargement / déchargement de bibliothèques dynamiques (.so), la glibc doit décider dans quel ordre initialiser les variables statiques. Les variables dépendent les unes des autres, dépendent de différentes fonctions, etc. En général, tout cela forme le graphe même dans lequel il y a des cycles et qui doit être trié.
Il était une fois, un code plutôt sous-optimal qui effectuait la tâche pour
O(n^2) était engagé dans cette tâche. Et en général, cela ne dérangeait personne, jusqu'à ce qu'en 2012, on
découvre que le code ne fonctionnait pas correctement et, dans certains cas, qu'il se trompait.
Les hommes durs de RedHat ont pensé, pensé et foiré quelques cycles de plus d'en haut. Les cas problématiques ont été réparés, mais l'algorithme a commencé à fonctionner pour
O(n^3) , et cela est déjà devenu visible et sur certaines applications, cela a commencé à prendre plusieurs dizaines de secondes, ce qui était un
bug en 2013. De plus, l'auteur du bogue a découvert des cas dans lesquels l'algorithme avec
O(n^3) également trompé . Il a suggéré d'utiliser l'algorithme Taryan, bien que le patch avec corrections n'ait jamais été conçu.
Et le temps a passé, la glibc a impitoyablement ralenti et en 2015, il y a
eu une autre tentative pour réparer l'algorithme . Malheureusement, sans succès, l'algorithme a été choisi
O(n^2) , en plus de confondre les branches du graphe, entre lesquelles l'ordre n'est pas défini.
Aujourd'hui est l'année 2019, la glibc continue de ralentir. À en juger par le temps qu'il m'a fallu pour résoudre le problème, les chances que je le résorbe sont nettement inférieures à 100%. Ceci est encore aggravé par le fait que les choses se passent en C, sans support IDE, dans le code de style de codage GNU, fou test runner ("si vous voulez relancer le test, supprimez simplement le fichier .out correspondant"). Et pour que la glibc puisse jeter un œil à votre patch, vous devez suivre la procédure d'
attribution des droits d'auteur , émettre correctement le patch et le diable sait quoi d'autre. Par conséquent, afin d'éliminer au moins le problème de l'invention d'un algorithme qui résout le problème, ce message a été écrit.